Ohhhhh. Man, that does suck. What you can't remove with Add or Remove Programs, use something like CCleaner to get rid of the Run keys in the registry. Then you can safely ignore it.
It sucks even more having to make floor model computers usable.
Um, you just should get all of the anti viruses, then take the best parts of each from the source code and make your own anti virus :P. Experienced hackers have made programs that sneak quietly below your AV's activity tolerance and can take the AV out, then do stuff and go away removing all traces anyway.