Using system restore (I assume this it what you used and not a format) and going back to a date where you were infected could reintroduce the virus. System Restore tries to help by giving you a second chance if you delete files in the system folders, unfortunately malware often installs itself in the system folders and when you delete it it could end up as a restore point waiting to bite you in the rear. So depending on the location of the infection it is often recommended you disable system restore and reboot.
You say various programs didn't work in getting rid of it, now without any information on why they didn't get rid of it (avast is good in giving an error message like file in use, etc.) I can't hazard a guess as to why, but it is usually location (and at no time have you mentioned that) or in use. In which case you can use the avast boot-time scan that runs before windows starts.
It is better to stop malware getting into the system folders and creating registry entries, etc.
You might also consider proactive protection, in order to place files in the system folders and create registry entries you need permission. Prevention is much better and theoretically easier than cure.
Whilst browsing or collecting email, etc. if you get infected then the malware by default inherits the same permissions that you have for your user account. So if the user account has administrator rights, the malware has administrator rights and can reap havoc. With limited rights the malware can't put files in the system folders, create registry entries, etc. This greatly reduces the potential harm that can be done by an undetected or first day virus, etc.
Check out the link to DropMyRights (in my signature below) - Browsing the Web and Reading E-mail Safely as an Administrator. This obviously applies to those NT based OSes that have administrator settings, winNT, win2k, winXP.
