Spyware is rampant throughout the internet. It is almost, if not impossible to browse the internet without encountering it. And as you mentioned, some anti-spyware software actually contain malware. The user thinks that he/she are taking action to rid their computer of malware when they are actually contaminating their computer.

This link discusses many products designed to remove spyware. Hopefully, the information will be helpful, especially the section for "trustworthy anti-spyware products".

http://www.spywarewarrior.com/rogue_anti-spyware.htm