I do IT work, and I've been almost exclusively handling the issues that come in about this exact problem from our users on Windows XP. Here are the things I've been doing to get rid of it. It's a bit more involved, but you're pretty sure to successfully remove just about all of the core components that make these apps work. I say "most" because I haven't found a way to know for sure if 100% of them are being removed; I know enough of them are to prevent the application from working anymore and, thus, causing you problems.
1. Reboot the PC and log in as Administrator (or an account, preferably not the one you typically log into, that has administrative rights).
2. Click this link to download a tool called "Roguefix."
It's basically just a batch file that has been hand-crafted by a group of guys specifically for these "rogue" anti-virus and spyware applications. Just save it to the desktop of the Administrator, or equivalently privileged, account.
3. Reboot the PC again, this time booting up into Safe Mode. You do this by hitting the "F8" key in that moment of black screen between your POST screen (that usually has your computer's manufacturer logo on it) and the Windows XP loading bar. I would suggest that as soon as your POST screen goes away, start hitting F8 repeatedly until you see the boot menu. THen just select "Safe Mode." You might have to hit "Enter" on the next screen if it asks you which Windows installation for which you want to run Safe Mode.
4. Once it's up in Safe Mode, log back in as Administrator. Once in, go to your Control Panel (Start > Control Panel, or Start > Settings > Control Panel), go into Folder Options, and in the View tab make sure you can see Hidden Files and Folders. Once that's set, use Windows Explorer to navigate to the following location:
C:Documents and Settings[username that you use most often]Local SettingsTemp
Delete everything in the folder, and back up one folder level. Go into Temporary Internet Files, and delete everything in that as well. Once done, navigate here:
Delete everything in it.
[TAKE A BREAK - This is rigorous for users not used to it, I realize! But we're almost done!
5. Once all those files are deleted, right-click your My Computer icon (either on your desktop or in your Start menu) and click Properties. Then, click the System Restore tab. Check "Disable System Restore," then Apply and OK to close the window.
6. Next, the moment you've been waiting for: Roguefix. Double-click the file that you saved to your Administrator desktop. An arcane looking red DOS-esque screen will appear. Simply follow the prompts, hit Enter when it asks, and select the "Yes" options for resetting Home Page and Wallpaper to default (just to be safe).
7. When finished, Reboot the PC back into Normal mode and log into your usual account.
8. If you use Internet Explorer, open it up before you do anything else, and go to Tools > Manage Add-ons. Go down the list of Add-ons and look for anything that has either a missing or questionable publisher, highlight it/them, and click the "Disable" radial button at the bottom. You'll have to do this for every one of them.
9. Close IE, re-open it, and go download a good anti-malware app. SpyBot is good for spyware and AVG is a good, free Anti-virus application, both come highly recommended in their respective fields.
I really hope this helps, and I'm sorry it's so long. It took me almost a week of research and trial and error to get this process down. Aside from a couple of *really* odd cases involving other, far more devious malware applications, this process has met with 100% success on our users' machines. Hopefully it will work for you, too.
If you wanna' message me or anything w/ questions or want an explanation of why I did what, I'll be glad to answer them best I can! Anyone else, feel free to pass this process on.