If you haven't I would run Spybot S&D which can be found at www.snapfiles.com
Make sure you are logged into a user that has administrative rights when running Spybot, so the program will have access to every profile. A lot of spyware programs have the ability to recreate themselves, so you could literally delete the file, hit refresh, and watch it reappear. At this point I don't know how they manage that but I'm assuming a loaded DLL file allows this action to take place. These are very hard to clean up.
The warning message you received just sounds like you use the fast switch method of logging on/off different users. A simple reboot will stop that message from appearing.