If someone is giving me fiat money, I know that I can spend that money as easliy as I got it.
Mostly correct but not always 100% true even with cash (i.e. serial number tracking to identify cash stolen in some large robberies).
The same thing should be with Bitcoin, so how are going to handle this issue?
Personally I don't see that "tainted coin tracking" should have anything to do with Bitcoin itself - policing is a job for police (and/or other government authorities) and is very much dependent upon laws that differ a lot between different jurisdictions.
A bitcoin should be fungible otherwise inevitably everyone's wallets will end up with "tainted" coins that they may have difficulty in using. New users have enough to cope with already without them also having to learn that "bitcoins are all equal, however, some bitcoins are not as equal as others".
BTW this issue has been discussed at length on this forum before (with a little searching you will discover a number of threads).