Malware trouble

I was using my computer the other day and a message at the bottom of the screen pops up with a big yellow triangle with an exclamation mark inside it saying "Dangerous malware infection was detected...." So I clicked on it and it automatically downloaded a program called Spyaxe that would scan, but it wouldn't let me delete any files without registering. Everytime I open internet explorer the home page has been changed to a system alert with all these links to download spyware programs. I also looked in my task manager and there is a file that I keep trying to close called mssearchnet.exe. Everytime I close it, it opens right away again. I have run AVG antivirus program, which finds trojan viruses everytime, I have run Spybot and Adaware. I just downloaded Xoftspy hoping that it will help. Any advice would be greatly appreciated!!!!