First, try this:
http://www.anti-spyware-101.com/remove-antivermins/ There is a download on that page that will scan for the AntiVermins spyware and tries to remove it. Hopefully that will work. You should also try downloading Spyware Doctor and running a scan with it. Apparently it will also detect it and, of course, all the other crap.