Tom Riddle was a promising student, but most people would not have met him. I don't recall any particular achievements of his that would have led to his face being featured in, for example, the Daily Prophet.
He took a low-key job at Borgin and Burkes, and was hardly ever in the spotlight.
I know that several teachers, Professor Slughorn amongst them,
suggested that he join the Ministry of Magic, offered to set up
appointments, put him in touch with useful contacts. He refused all
offers. The next thing the staff knew, Voldemort was working at Borgin
Harry Potter and the Half-Blood Prince
Once he had become a "snake-faced mystery man," yes
Of course, most people had would not have seen Voldemort personally. But, as you mention, Dumbledore, the Order, and the Ministry (via Aurors) would all have seen him in combat. I see no reason that they would not have disseminated information about his appearance throughout the magical community.
Moreover, some of the Order members knew what he looked like. Surely they would have informed their family and friends? And we know how rumor spreads.... The same goes for Harry, but even more so.
In any case, people would assume that it was Voldemort if a snake-faced man showed up at their door. Snakes are heavily associated with Dark Magic, and certainly at this point everyone is aware that the premier Dark Wizard is Lord Voldemort. So in that sense alone, they would recognize him, since they would instantly know it was he.
We also have some evidence from the books:
Both Williamson and Fudge recognized Voldemort when he appeared in the Ministry:
"He was there!" shouted a scarlet-robed man with a ponytail, who was
pointing at a pile of golden rubble on the other side of the hall,
where Bellatrix had lain trapped only moments before. "I saw him, Mr
Fudge, I swear it was You-Know-Who, he grabbed a woman and
"I know, Williamson, I know, I saw him too!" gibbered
Fudge, who was wearing pyjamas under his pinstriped cloak and was
gasping as though he had just run miles.
Harry Potter and the Order of the Phoenix
Of course, Williamson is an Auror and Fudge is his boss.
But even Grindelwald, who had been locked in a cell in his own prison for five decades, recognized Voldemort immediately:
The emaciated figure stirred beneath its thin blanket and rolled over
toward him, eyes opening in a skull of a face. . . . The frail man sat
up, great sunken eyes fixed upon him, upon Voldemort, and then he
smiled. Most of his teeth were gone. . . .
“So, you have come. I
thought you would . . . one day. But your journey was pointless. I
never had it.”
Harry Potter and the Deathly Hallows
And of course, as Sphoorthy Nutulapati mentioned, there was a woman in mainland Europe who also seemed to recognize him:
“Gregorovitch?” said a high, cold voice.
She shook her head: She was trying to close the door. A white hand
held it steady, prevented her shutting him out. . . .
“I want Gregorovitch.”
“Er wohnt hier nicht mehr!” she cried, shaking her head. “He no live
here! He no live here! I know him not!”
Harry Potter and the Deathly Hallows
Finally, Remus Lupin appeared to expect students to recognize Voldemort on sight (and to be more afraid of him than of giant spiders or banshees):
"Well," said Lupin, frowning slightly, "I assumed that if the boggart
faced you, it would assume the shape of Lord Voldemort."
Not only was this the last answer he'd expected, but Lupin had said
Voldemort's name. The only person Harry had ever heard say the name
aloud (apart from himself) was Professor Dumbledore.
"Clearly, I was
wrong," said Lupin, still frowning at Harry. "But I didn't think it a
good idea for Lord Voldemort to materialize in the staffroom. I
imagined that people would panic."