Most executables on their own, pose little threat, unless they have been coded in such a way as to be independant. Sometimes, those same executables rely on DLL files to point to certain locations or for referencing of comands. It is possible, that although the registry entry and the executables have been removed the entries in said DLLs still exist.
What about "run" or "runonce" in the registry? Did you clean those aswell?
Not all files will be identifed by their exact name in the registry, some can be identified by a string {abcde-fghijkl-12345-...} and thus not removed/found when manunally cleaning the registry.
Try opening up Microsoft's System configuration utility (msconfig) and in the "startup tab" look for or identify any "missing entries". An entry with no name, pointing to a registry entry nonetheless, chances are that's your culprit.
Other times, some of these buggers load up into a higher level of memory and rewrite themselves. Those are harder to get rid of.
You said, you identified them as Trojans, could they actually be malware? Have you tried a malware scanner or registry cleaner?