Antivirus Program didn't work this time!

I had Avast installed, but when I noticed that it never updated itself, nor gave me the option to, I uninstalled it, and installed Microsoft Security. I still got a virus. I tried to put avast back on, but Got the message "setup cannot be downloaded" when I tried to execute the startup file. I've gone through the CP add/remove but the AV programs are not listed. How can I remove all traces of the previous AV install attempts so that I can get a "fresh start"?:confused