My understanding is that JKR had all the major plot points of the main story already decided upon and outlined from the start. Voldemort name/anagram play would have been a necessary detail from the get go.
Her subsequent job was to flesh out the outlines. What she did that was exceptional was to add many more layers of secondary plots weaved into the main one and to add many interesting and quirky details. If you think about it you can see that the main plot would have barely made a book.
EDIT/ ON NAMES:
MARVOLO sounds like marvel, marvelous his mother literally named him Thomas "the marvel" riddle, or since she was so infatuated with his father the "marvelous" could directly refer to tom riddle or be the "gift" that the left her. Marvolo could be humorous in reference to her father, one of the last descendant of the Gaunts, a "marvelous" ignorant man living in squalor. Finally the Marvolo also provides a link to the VOL of Voldemort.
VOLDEMORT doesn’t seem like an accident at all; it literally means “flight of the Death” also VOL also means THEFT in French so it is “Theft of Death”, as in someone cheating death, like a DEATHEATER, sounds familiar? The modern French origin is confirmed by JKR insistence that it is pronounced "MOR" and not "MORT" like "la Morte d'arthur" in old French. also her grandfather was French, she studied French at uni and lived in Paris for a while though she made mistakes using “she is charmant, your aunt” instead of “charmante”, though it could be for the benefit of the average reader.
So, since it is probable that Voldemort, and possibly Marvolo was intended, it is Tom Riddle that must have been added, though the boy being a “riddle” is possible, he wasn’t such a riddle and was pretty consistently nasty throughout.
"I generally think you're correct here, but providing a quote where JKR has said that she had a lot of stuff plotted out ahead of time would go a long way here. – phantom42 1 hour ago"
i definitely remember her speaking, back then, about little kids trying to break into her house to read the outlines and notes of the next books. Also there is interview where she spoke about the story genesis during her train ride to London. i also seem to remember, that she said somewhere that she had about 50 pages of outlines and notes for each book, but i may be wrong and couldn't find references for this.
HERE ARE SOME REFERENCES/
i did a search since some wanted references, i didn't find everything but here/
"The book's last chapter was one of the earliest things she wrote in the entire series." "Rowling to kill two in final book". London: BBC News. 27 June 2006 “She told the Richard and Judy show that she had long known how the series would end, because she had written the last chapter "in something like 1990".” Rowling to kill two in final book.
How J.K. Rowling Plotted Harry Potter with a Hand-Drawn Spreadsheet in Books, Writing | July 1st, 2014 How J.K. Rowling Plotted Harry Potter with a Hand-Drawn Spreadsheet.
Interview With J. K. Rowling On February 3, 2000. “I always have a basic plot outline, but I like to leave some things to be decided while I write. It's more fun. :-) “
Interview by Borders Online 1999 A Conversation With J.K. Rowling The Harry Potter Books.
“I was taking a long train journey from Manchester to London in England and the idea for Harry just fell into my head. At that point it was essentially the idea for a boy who didn't know he was a wizard, and the wizard school he ended up going to.” And “JKR: I always conceived it as a seven-book series”
“J.K. Rowling, it is well understood, has boxes and boxes of notes on the Harry Potter series. Obviously not every detail made it into the books, but from what descriptions there are, it is clear she really knows her characters, their histories and their story arcs, and she really knows the direction in which the plot is moving. She writes with authority—she knows what she’s talking about” How To Decide If You Should Plot Outline Or Freestyle It.
“Some of them are invented. Voldemort is an invented name. Malfoy is an invented name. Quiddich is invented. […]But it is a lot of work to create an entire world and it was about 5 years to finish the first book, to plot the remaining 6 books, because they were already plotted before the first book was published and Book 2 was started before Book 1 was finished. Yeah, so I spent an awful lot of time thinking about the details of the world and working it out in depth.”[…] I have a basic structure for each book, but sometimes I’ll decide we’ll play around with that middle section because I don’t much like it as much as I did back in 1992 when I originally found it.[…] Names are really crucial to me. Some of my characters have had 8 or 9 names before I hit the right one. And for some reason, I just can’t move on until I know I’ve called them the right thing. That’s very fundamental to me." J.K. Rowling interview transcript, The Connection (WBUR Radio), 12 October, 1999.
“However, Marvolo also clearly suggests marvels, as befits a pureblood wizard, as well as Shakespearean names such as Malvolio (Twelfth Night).” Baby Name Wizard.
From Harry Potter: Is "Marvolo" a real name? “Marvolo is most likely a variation on Malvolio, a name with Latin origins meaning "ill will", as well as a fairly famous character from Shakespeare's Twelfth Night.” From Harry Potter: Is "Marvolo" a real name?
“Lord Voldemort, meaning ‘flight of death’ in French, has been difficult to translate as his real name “ Marvolo (Wordnik)
According to an interview with Rowling, "Voldemort" is pronounced with a silent 't' at the end, as in the French word "mort", meaning "death". […]In a 2001 interview, Rowling said Voldemort was invented as a nemesis for Harry Potter (the main protagonist of the series), and she intentionally did not flesh out Voldemort's backstory at first Lord Voldemort (Wikipedia).
There is also a long discussion on Voldemort/Riddle on The Straight Dope.