made up of many different files. An .exe or two, some .dll's, an .ini, registry entries....
Some of them even bury portions of themselves in the alternate data stream, which is not normally viewable without a hex editor. (See rootkits.)
In your case this was a rogue product designed to be hard to remove, the files are hidden all over the place.
If your security program can't find the files you haven't really got much chance, unless you know what to look for and how to submit them. Most of the AV companies have a submission procedure, often invoked from within the GUI of the program itself.
(For example, with mine you zip the virus/suspect file, password protect it, and email it to the company.)
You're right to be indignant. These things are quite prevalent. You shouldn't have to be a semi-expert to protect an OS, but these days, you do need to learn how to. There is no silver bullet. MS already know these things exist.(And they're evolving. Vista was supposed to be a secure platform. Hah.) Best you can do is learn about layered defenses.