Does your video card come with 512MB of RAM or were you referring to your main computer memory.
What is your budget? This would be a big help.
And even though a fresh install of Windows on a clean HDD is preferrable, as long as you have the Windows CD, you can do a repair install. That's what I did a couple of years back on my XP system when I replaced my ECS mobo with my current ASUS mobo.
You shouldn't lose your data but I'd back it up just in case something goes wrong. Even though it's a Windows repair, if I remember correctly, I still had to reinstall every program again because they wouldn't work. But don't quote me on that.
I will assume one thing and that is to keep cost down and to reuse your memory and video card.
CPU: Athlon 3700+ San Diego Socket 939 - $93. Now, if you are into overclocking, then I suggest you getting the OEM part at ewiz.com as they are the cheapest that I could currently find for an OEM 3700. And then get an Arctic Cooling Freezer 64 Pro at Monarch for 23 bucks. You'll probably be able to OC it to at least 2.6 GHz and maybe to 2.8 if you are lucky.
Mobo: ASRock 939Dual - $75
Memory: If you already have a gig of main memory then nothing here until you upgrade to VISTA, then you'll need another gig. Otherwise upgrade to one gig. If you have 1x512MB, then get another 1x512MB of the same memory to be on the safe side. If you have 2x256MB, then I suggest you getting 1x1GB stick so you can buy another 1gig stick in the future. You may lose dual-channel but it's only around 10% performance loss for most applications anyway.
So, the total is less than 300 dollars.