How did Cornelius Fudge recognize Voldemort's return?

Question

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.

Answer 1

There was a great passage of time, about 25 years, between when Voldemort created the horcrux from the diadem to when he fell from power in 1981:

Ravenclaw Diadem - circa 1956 - Following the murder of an Albanian peasant. After Dumbledore was made headmaster, Voldemort resurfaced and asked Dumbledore for the Defence Against the Dark Arts position, which Dumbledore denied him. It was during this visit that Voldemort was thought to have hidden the diadem in the Room of Requirement. Voldemort's age: ~30 source answer

But yet even by that time his features had began to turn:

Voldemort had entered the room. His features were not those Harry had seen emerge from the great stone cauldron almost two years before; they were not as snake-like, the eyes were not yet scarlet, the face not yet masklike, and yet he was no longer handsome Tom Riddle. It was as though his features had been burned and blurred; they were waxy and oddly distorted, and the whites of his eyes now had a permanently bloody look, though the pupils were not yet the slits that Harry knew they would become.

_{Half-Blood Prince, Chapter 20, Lord Voldemort's Request}

This was noted by Dumbledore as his suspicions of the multiple horcruxes was confirmed:

"Yet it fitted: Lord Voldemort had seemed to grow less human with the passing years, and the transformation he had undergone seemed to me to be only explicable if his soul was mutilated beyond the realms of what we might call usual evil..."

_{Half-Blood Prince, Chapter 23, Horcruxes}

Fudge would therefore have known Lord Voldemort in his current appearance.

Answer 2

Voldemort looked the same as before.

Fudge was able to recognize Voldemort because the reborn Voldemort looked as he did before his years-long disappearance. While he isn’t explicitly described on the night he kills the Potters, his appearance is unusual enough to scare a Muggle child.

“Nice costume, Mister!’

He saw the small boy’s smile falter as he ran near enough to see beneath the hood of the cloak, saw the fear cloud his painted face: then the child turned and ran away … beneath the robe he fingered the handle of his wand … one simple movement and the child would never reach his mother … but unnecessary, quite unnecessary …”
_{^{- Harry Potter and the Deathly Hallows, Chapter 17 (Bathilda’s Secret)}}

When Voldemort was returned to a body, he looked the same as when he killed the Potters, since when Harry witnesses his ‘rebirth’ he describes staring back at the face that haunted his nightmares. He’s almost certainly referring to his recurring nightmares about the night Voldemort killed his parents, because while he saw Voldemort on the back of Quirrell’s head, he’s never mentioned having any nightmares about that, and he is mentioned several times having nightmares about when his parents were killed.

“The thin man stepped out of the cauldron, staring at Harry … and Harry stared back into the face that had haunted his nightmares for three years.”
_{^{- Harry Potter and the Goblet of Fire, Chapter 32 (Flesh, Blood and Bone)}}

As for why Voldemort’s appearance changed again between his meeting with Dumbledore when he hid Ravenclaw’s diadem in Hogwarts and when he killed the Potters, it is possible that there is also a more gradual component to the changes in appearance that are caused by creating Horcruxes. The changes may not all happen immediately after the creation of each additional Horcrux. His appearance may have changed in a more gradual way as well.

“I, who have gone further than anybody along the path that leads to immortality.” That was what you told me he said. “Further than anybody.” And I thought I knew what that meant, though the Death Eaters did not. He was referring to his Horcruxes, Horcruxes in the plural, Harry, which I do not believe any other wizard has ever had. Yet it fitted: Lord Voldemort had seemed to grow less human with the passing years, and the transformation he had undergone seemed to me to be only explicable if his soul was mutilated beyond the realms of what we might call usual evil …”
_{^{- Harry Potter and the Half-Blood Prince, Chapter 23 (Horcruxes)}}

Dumbledore never says exactly how or when creating Horcruxes transforms someone, so he didn’t necessarily mean that it happens all at once after creating additional Horcruxes. Therefore, it’s possible Voldemort’s appearance could have changed further without him making more Horcruxes.