In Goblet of Fire, Voldemort tells the Death Eaters at the Little Hangleton graveyard how he needed his father's bone to regenerate. The fourth and sixth books imply that Little Hangleton is definitely a small, primarily Muggle community. The Death Eaters would have been able to reason out Voldemort's likely blood status from this information alone, if they wished. They could also easily have glanced at the gravestone Harry had been bound to and seen the name of Voldemort's father -- "Riddle" -- and, being mostly interrelated purebloods themselves, they would know that there was no pureblood Riddle family in Britain.
And more to the point, he outright tells the Death Eaters his father is a muggle.
"You think I was going to use my filthy Muggle father's name forever? I, in whose veins runs the blood of Salazar Slytherin himself, through my mother's side? I, keep the name of a foul, common Muggle, who abandoned me even before I was born, just because he found out his wife was a witch? No, Harry - I fashioned myself a new name, a name I knew wizards everywhere would one day fear to speak, when I had become the greatest sorcerer in the world!"
None of them seem surprised to hear this, so apparently they already knew.
Barty Crouch Jr. already knew Voldemort was Tom Riddle Jr. and could easily have learned that Tom Riddle Sr. was a muggle. He alluded to this when he spoke to Harry.
The Dark Lord and I", said Moody, and he looked completely insane now, towering over Harry, leering down at him, "have much in common. Both of us, for instance, had very disappointing fathers... very disappointing indeed. Both of us suffered the indignity, Harry, of being named after those fathers. And both of us had the pleasure... the very great pleasure... of killing our fathers to ensure the continued rise of the Dark Order!".
When did the Death Eaters learn the leader of their pure-blood ideology was a half-blood? Did they learn back when Tom was a student at Hogwarts? During the First Wizarding War? Some other time?