We know that the Voldemort of GOF didn't look like the Voldemort of 13 years before. The last Horcrux he made before trying to kill baby Harry was the diadem, which he later hides in Hogwarts. While hiding it at Hogwarts, Voldemort's described as:
Voldemort had entered the room. His features were not those Harry had seen emerge from the great stone cauldron almost two years ago: They were not as snake-like, the eyes were not yet scarlet, the face not yet masklike.
Clearly Voldemort has a new look when he returns in GOF, after he had a new body and created another horcrux (Nagini), which we know change the creator's look. He's described as "Whiter than a skull, with wide, livid scarlet eyes and a nose that was flat as a snakes with slits for nostrils ."
So why does Fudge, who for the past year has been trying to prove Voldemort didn't return, just believe Voldemort returned by seeing a completely different face than the one he associated to Voldemort?
Shouldn't he, of all people, just say it's polyjuice potion, or a spell that changes one's appearance, such as the one Ron used when they broke into Gringotts in DH?
Also, another ministry member swears it's You-Know-Who, which just doesn't fit as he's seeing him for the first time:
'I saw him, Mr Fudge, I swear it was You-Know-Who, he grabbed a woman and Disapparated!'
'I know, Williamson, I know, I saw him too!' gibbered Fudge.