BECAUSE IT MAKES YOU FEEL BETTER TO YELL ABOUT STUFF.
Also: Hi, I’m new to post and a long time lurker. And I can’t think of much more to say then that.
The success rate is 100% if you know what you’re doing, worst case scenario, you have to remove entries from the local settings folder or installshield folder.
LOUD NOISES!
ontopic: ccleaner all the way - has registry scan, is free, easy, and doesnt require tedious searching in the reg folder yourself. in the minutes saved you can make yourself a sandwich or something. awesome!
CCleaner is good, but seriously… if you know what you’re doing in the registry, you can almost always be more efficient in the cleanup if you do it manually.
If you’re worried, make a reg backup or a system restore point.
REGEDIT FAGGGOTTTT
I second the motion for CCleaner. It has a bunch of options for removing old temporary files, and for scanning the registry, backing it up, and then deleting the broken parts that no longer point to any valid files (could be handy with this missing GoW situation you’re having, I think).
If that doesn’t fix it, I also second the motion for manually editing the registry. Manually editing the registry can only make it worse if you really (and I mean really) screw something up, and even then it won’t necessarily result in a totally unfixable situation. It’s really not that difficult, just as long as you’re careful and make sure to back edited keys up by right clicking them, and then clicking Export, before changing them.
The first places to look for latent footprints of uninstalled programs would be in the software branches (always, always look there first). There are two main software branches, one for your current User, and one for the Machine as a whole. They’re located under “HKEY_CURRENT_USER/Software” and “HKEY_LOCAL_MACHINE/Software”. Browsing these trees and finding programs in there should be fairly self-explanatory. It only gets a bit tricky (in my experience) when Microsoft is involved (go figure 
) because the Software/Microsoft key is somewhat disorganized, IMHO. (Most common Windows-related stuff will be located under Software/Microsoft/Windows/CurrentVersion, if you’re curious – just FYI.)
At any rate, as far as Gears of War is concerned, I googled a bit, and it seems that it should be located under either “HKEY_CURRENT_USER/Software/Microsoft/Microsoft Games/Gears of War” or “HKEY_LOCAL_MACHINE/Software/Microsoft/Microsoft Games/Gears of War”, so you might have a look there, maybe try deleting those keys if they still exist (back them up first, just in case!) and see if that fixes your problem by rerunning the installer.
Another good place to look for remaining registry keys after an uninstall fails, would be under “HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall”. Most Add and Remove Programs should be located here. The keys (folders) themselves are kind of illegible (most are GUIDs) but you can still easily identify a program in this particular list by opening one of the GUID keys, and taking note of the “DisplayName” value in the right hand pane – DisplayName shows the program as it appears in Add and Remove Programs. Personally, I don’t actually recommend removing broken add/remove program entries yourself if you’re not confident with the registry yet, especially since CCleaner has a feature to remove broken Add/Remove entries built in already – it makes it really easy (another reason to give CCleaner a shot, if you haven’t yet!)
Anyway, sorry for the lengthy post – hope that helps at least somewhat, if at all. Hope you find a fix for your problem soon! 
tl;dr - I second the vote for trying CCleaner! (Can’t vouch for Revo Uninstaller, I’ve never used it myself.) Good luck!
I already do it manually every night just by habit. Clear all the temp folders, recent folder and ie/ff cache.
Yeah, I find picking up garbage, hair, lint, food crumbs and such off the floor is way better than using a vacuum cleaner.
Haha, that’s a good point… but while a vacuum cleaner may be good for crumbs and dust, it can’t pick up or fold your socks!
Just wanted to point out that sometimes manually editing the registry really is unavoidable, when there aren’t any programs out there to fix the specific problem that’s occurring. (And sometimes they don’t detect and clean up the entire mess.) Although, you’re right, this particular case doesn’t sound too messy. I think it should be pretty obvious to CCleaner or most any other competent registry-fixer-upper to detect the missing game files and clean the registry accordingly.
Oh, also, something I forgot to mention earlier to the OP: If you do go the CCleaner route, make sure to scan the registry and clean it multiple times. As it turns out, deleting broken registry keys can break other registry keys, which all need to be fixed in turn. Just keep scanning, backing up, and deleting the broken keys until CCleaner doesn’t detect any more problems. You shouldn’t have to scan more than 3 or 4 times before everything that CCleaner can detect has been fixed.