We know from the end of Goblet of Fire that a number of Death Eaters were found innocent, at around the same time that Sirius was convicted:
'Look, I saw Voldemort come back!' Harry shouted. He tried to get out of bed again, but Mrs Weasley forced him back. 'I saw the Death Eaters! I can give you their names! Lucius Malfoy -'
Snape made a suddent movement, but as Harry looked at him, Snape's eyes flew back to Fudge.
'Malfoy was cleared!' said Fudge, visibly affronted. 'A very old family - donations to excellent causes -'
'Macnair!' Harry continued.
'Also cleared! Now working for the Ministry!'
'Avery - Nott - Crabbe - Goyle -'
'You are merely repeating the names of those who were acquitted of being Death Eaters thirteen years ago!' said Fudge angrily.
We know these Death Eaters had Dark Marks, because that is how Voldemort summoned them to him after his resurrection.
The only reasonable conclusion is that either the Dark Marks were invisible or that the Ministry simply did not know to look for them.
It would be a sensible precaution on Voldemort's part to have designed the Dark Marks to be invisible except when he wished them to be seen, and personally this is my preferred interpretation. We do know that they change in some way according to his wishes.
However, I believe Hermione made a comment at one point about it being obvious even to the Ministry that Sirius was innocent (after his death) because he didn't have a Dark Mark. That suggests that the Dark Marks are visible, but perhaps indistinct enough to be overlooked if you don't know what you're looking for, and that the Ministry didn't know about them until after the battle at the end of Order of the Phoenix. (Of course, Snape told Fudge about them at the end of Goblet of Fire but Fudge didn't want to believe it.)
Dumbledore presumably knew about them from Snape, and could have told the Ministry about them during the first war or after Voldemort's disappearance. However, if he had done so, it would not have been possible for Snape to pretend to have remained loyal to Voldemort, and Dumbledore may well have felt (correctly, as it turned out!) that this was more important.
