Ah, you have got to hate that.

Perhaps try out Spybot: Search and Destroy. That's a fairly decent program, you could also try out Avast! which is a virus scanner that I've been using recently and it seems alright.

Other than that, I'm not quite sure how to manually go through and delete said toolbar and spyware.