It seems you have already done all this, but the normal route would be....
The virus is in certain Windows start-up files, and disinfection is not permanent because it reappears at next boot. It takes an expert to remove this problem without having to reinstall Windows, and the chances are probably not good.
I would recommend a hard disk wipe and reinstall. You want to get data off first? Write a bootable CD - say Ubuntu linux would be fine. With that booted, you can transfer all your important stuff to backup.
You might like to replace the bios first of all, just in case of a bios virus (never heard of one, but best to be safe), followed by reinstall of Windows, including SP3, install anti-virus (Avast recommended), firewall (zonealam recommended), then finally update all recent patches form MS update and your data. The virus could of course be in your data too, so a complete, deep scan would be a good idea - preferably before replacing on your hard drive.
Since you are having trouble keeping a clean system, some people would say the infection is actually in one of your defensive programs, maybe Norton AV, so I would not install that at all, IMHO Avast is much better. Same goes for Windows messanger etc. You will find that Avast has 7 specialised defenses for things like email, network, browsing, P2P, messaging, etc etc which is why it seems better to me. Free too !