I'm sure it's been answered however I'll try to break it down into a simple answer and throw in a few things that may not have been presented.
1) First of all, every system is different. Now this is blatently obviouse to most people but when it comes down to it the problem first lies within the Windows core operational "system" for lack of a better word. I.E System32, System, and of course your Registry. Compare this to Unix based operating systems and the core problem is very simply the Windows Kernel and Registry, for the most part, and in most (even advanced users) systems has left over DLL's, Registry Entries, broken paths and simply put "junk files" left over from installation and removal of software, spy-ware, viral infections, installation, SP upgrades... the list goes on. Whereas with Unix based operating systems most users know what should and should not be in their /bin /usr/bin and fstab etc. Making it much easier to "clean house". There is also a lot of "bloatware" which simply is what it sounds like. Mix that with a lot of applications that come with poor quality removers that iether purposfully leave files behind or do so in simple laziness from the development team.
2) Because of the above mentioned issues (which hopefully gives a basis to understand what you're in effect 'clearning) different "cleaners" work in different ways. Some simply look for active references between the system->reg->low level data. Others simply clear out your temporary files (offline/online) and remove rogue DLL's and invalid reg keys, some do both and others take it a step further and may create a sort of "sub shell" within the application to test each DLL and reg entry followed by removal of suspected leftovers. (For the advanced users please bear with the very low level explanation)
So basically it's like having a friend of the family clean your house. He will decide what is and what is not garbage by trying to reference what it belongs to, why, when it was last used and whether it still works. Different cleaners look for different attributes and thus come out with different results. Some are more "cautious" than others, some are known to be more dangerous to amateur users as you need to know what you are actually approving the removal off (specially when you are running corp applications that aren't digitally signed, dual booting etc).
And finally sometimes while you are running a cleaner an application or perhaps even yourself browsing the web will end up downloading additional temp files and cookies after that directory has been scanned therefore leading to files being present when you re-scan. As a general rule I always Defrag and run Malware/Spyware and on the rare occasion CCleaner but I do so offline.
Hope that helps a little.