Sounds like thats the problem sorted (for now at least
) so don't really need to do anything else at the moment.
The keyboard service problem is apparently a known bug that has existed from driver version 3.5 onwards - they just haven't fixed it. You should be perfectly safe leaving it disabled.
(Probably worth checking that any further updates to your system don't re-install the ATI keyboard service though
)
ATI icon and sticky keys - I wouldn't bother with those at present.
AdAware does a similar job to Spybot but each picks up things the other doesn't. That was the fix in case it was spyware related. Always good to have at least one of those products installed anyways.
Not worth rolling back - would keep that as a last resort if the problem reappears at some point in the future. (And shutting down the keyboard service, icon and sticky keys have failed to fix).
One other thing you may want to consider doing, unrelated to your problem but should improve your internet surfing. If you haven't done so already - run the services.msc again and STOP and then DISABLE the 'Messenger' service. This is not internet messenger but a 'feature' of XP thats intended to be used by network printers etc. for putting alerts on your screen. Unfortunately Microsoft don't check that these messages come from your local network and so spammers have been sending messages using it. These then pop-up on your screen with such great titles as "click here to find out how you can spam thousands of people" >
. Disabling it stops that little exploit.