Hi Churchmouse,
Some rootkit scanners are more user friendly than others. Those from AVG, F-Secure, Panda are fine for the less “technically-savvy”, although some legitimate applications do hide processes, so always check any detections on Google.
You can have more than one copy of AVG Anti-Spyware and it will run as an on-demand scanner (non-residential) after the trial period has finished- I’d definitely recommend a scan with this product.
Try removing Ad-Aware and reinstalling it. I’ve had no problems with reliability and it always finds things on infected computers. Whether or not it has the best detection rate I don’t know- my approach is to run multiple free scans because they all pick up different scans.
Try scanning in Safe Mode with Spybot, Ad-Aware and AVG Anti-Spyware, as this can help with detection and removal.
http://www.pchell.com/support/safemode.shtml
To fix your icon problem, try downloading TweakUI and running the option to rebuild icons:
http://www.microsoft.com/windowsxp/downloads/powertoys/xppowertoys.mspx
http://donaldbroatch.users.btopenworld.com/tweakui.png