Got a virus, it wont delete, please help!?

I have got a virus on my computer. (Came with a Email)

So i installed ZoneAlarm (Zonelabs.com) and AVG Anti-Virus Free (free.grisoft.com) and i CANT GET RID OF THE VIRUS!

It pops up some notifications in the notification area with some red button and a exclamation mark on it.

Apart from that there are two dialogs, one which is called Windows Security Alert (And the text doesnt seem like ANYTHING microsoft would write), it says "Click here to download spyware remover" and another that says i got a worm blah blah on my system 2000/XP Home/XP Professional/Vista Business.

I am running XP Pro and i have a Vista Ultimate partition (And a Ubuntu Linux)

It also adds three icons to the desktop "Error Cleaner" "Provacy Protector" "Spyware%26Malware Protection"

I just cant get rid of it, AVG has searched 2 (On the third lap right now) on Full, i have removed several Start up items that wherent there before and so on...

What else CAN i do? My system is so slow right now that it is barely useable..

Got a virus, it wont delete, please help!?virus removal

It is spyware masquerading as a security alert. You probably don't have a virus as claimed, just the spyware of the company trying to sell this software to you, it's just claiming you do to scare you into buying their useless software. You, however, are infected by it, so you need to get rid of it.