Have you checked for apps that run when windows starts from the reg key:
[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\RunOnce]
Check the timestamps on all exes mentioned in here and look at the company name, product name etc using the props window in Windows explorer . If the file is only a couple of months old and looks like a system file e.g loader.exe but company and product name are blank (instead of Microsoft) then it is probably bogus.
Deleting all the suspect values in this key should stop em starting.
Another place to check would be c:\WinNT\system and sort by file date, again if there is anything that is newish it could be fishy.
To find which apps are writing to the registry you can use regmon from sysinternals.com
http://www.sysinternals.com/ntw2k/source/regmon.shtml
It has a log bootup option that will log every registry access as the system initializes. If you know the reg keys that get written then you can filter on this and identify the .exe doing the writing.