I would say that it's better to use an assortment of Spyware removal programs. Since spyware removal programs aren't like Anti-viruses it's all right to use a few of them together to be extra safe. I've also used Spybot Search and destroy for a while, but it's just the same (well a little difference here and there) as any other spyware remover.

Personally I use Adaware and the Spyware remover that came with my anti-virus suite. And use other spyware removers here and there. I would say that you should give Adaware a try as well. I know many corporations (banks actually) where the IT department uses Adware as their primary spyware remover tools.

Edit: May be you are talking about slow start up's and shutdowns? If so then you might have to remove a few unnecessary programs from the start up list, or perhaps tweak the registry to have faster shut downs...