If you want to remove the leftovers, then there's nothing stopping you. You can remove registry entries with the registry editor and you can delete files with Windows Explorer or at the command line or however you choose.
But if you're asking how to identify those leftovers, that of course depends on the program you just uninstalled. Poke around in the "Program Files" directory if you want. Personally I have a 2-GB hard drive so it isn't worth my time to bother.
And I disagree that uninstalling software should delete everything related to it. Recently I installed Firefox 2.0. I also installed some other rubbish that I didn't want, so I went and uninstalled that. And while I was doing that, I decided to get rid of other things I didn't need. Like Firefox 1.7 and Firefox 1.8. This had the unfortunate side effect of deleting a file named "Firefox.exe" and meant I couldn't run Firefox 2.0 without downloading and installing it again. So I did that, and when I started up Firefox all of my configuration was still there. Bookmarks, home pages, proxy server name, everything. That wouldn't have happened if the uninstalls had done "the right thing", and that's why uninstalling software commonly leaves files and registry entries behind.