A. when you uninstall, the process in question was not terminated and locked the file so it it could not be removed while the process was still running. viruses commonly do this but so do some applications
B: the uninstall procedure failed to remove the RUN/STARTUP registry entry for it.
You *might* use regedit to remove mention of it in the registry(simple BUT be sure you know what your doing)
When *I* i have to deal with an ornery virus that won;t die, I generally locate the virus file FIRST, boot up a LIVECD copy of ubuntu, make a directory called BAD,move the virus into it, make a directory in the same location of the virus with the exact same filename(and extension) and reboot windows. Then deal with the (file not found popup) consequences.