Have you tried Ad Aware? Look at
http://www.lavasoft.nu/support/download/#free and see if that helps your problem. It offers a setting where it will scan your computer and remove spyware before anything actually starts up. It's free.
I also take it you've tried uninstalling PurityScan from the add/remove programs thing in Control Panel?
Let me know if there's anything else I can do to help.