Only the very best application developers that care about the total user experience take the additional hour to write the necessary install/uninstall routines that remove *all* traces of their program. And by all traces I mean registry entries, temporary files, special .dll files, custom settings, .ini files, windows' settings, shortcuts, empty directories & folders, user generated data and configurations and profiles, drivers, and so on and so forth.
The main obstacle to doing this is none other than carelessness and laziness. The programmer knows exactly what is added to the system and thus also knows what to remove. Whadda'ya know! They're both the same thing! There are no tricks or gimmicks involved here. This is not rocket science. This is laziness.
Good programming would also dictate that if user-generated settings and configurations are placed in any section of the registry - they should be made known to the uninstaller. This is not difficult either. And if there are updates to the program. The update installer can be made to make amendments to the original installation record, or simply be all-inclusive. Again, this isn't hard. The uninstaller can highlight differences between what was originally added at setup time and what exists now.
When you go to remove something, the uninstaller would remove what it knows. If it finds additional material it cannot reconcile - it should alert you with enough information so that you can take further action yourself. If questions or conflicts arise during removal; the issue and operation in question can be presented to the user in a clear & concise dialog box or output to a text file on the desktop. I've seen examples of all the above behavior taking place.
While there are well-behaved programs that do their best to abide by the leave-no-mess-behind philosophy, I tend to always recommend portable-style applications. By this I mean programs that can be installed by manually copying them to the Programs directory and making a shortcut yourself. Ideally the program would keep all its settings to itself in a .ini file in the same folder. And this works well for the small stuff, but when it comes to productivity suites, media, internet.. forget it. Sure, you can get these things to behave like portable-leave-no-mess-behind stuff. But doing so requires more advanced knowledge on the user's part to set it up.
Personally, myself, I like to "test install" new things on another system which is "disposable" and can be immediately restored from disk image. A sandboxed VM works well here too. Once I am satisfied that the program is useful to me it becomes a keeper. And at that point I could care less about how much it sprawls itself all over town. And if I have to remove it, which is rare, I'll go romping through the stuff I listed in the first paragraph.
A lot of this "portable" way-of-doing-things takes some effort. It requires you understand folder hierarchies and know the difference between 4 major types of data, UserData, OperatingSystem, Programs/Applications, and Settings. Not to mention where all that stuff is located. This is way way too much for today's dumbed-down users. You can thank smartphones and tablets for fueling this fire. And the problem is only going to get worse. Besides, when a phone or tablet goes bad, the first thing you are taught to do is reset it anyways.
We used to work this way in the old-school 8-bit days of the Apple II. And while today's systems are infinitely more capable when compared against the old dinosaurs they could benefit from a dose of simplicity and straightforwardness.