I know that it's possible to sort through the blockchain history for your bitcoins, however it is difficult to trace back your coins to when they were originally mined due to bitcoin mixers. Is it possible to create a tool that will give a complete history of your coins? More specifically, is it conceivable that at some point regulators may distinguish between "dirty" and "clean" bitcoins, where "dirty" bitcoins are anything that have passed through a wallet of a known criminal? Even with bitcoin mixers?
The tool for complete history of all bitcoin minted already exist and its called blockchain. You can see all history here (random transaction selected)
There is a term taint and it's meaning how two addresses are connected. It partially explained here What are tainted coins exactly?
Bitcoin is not a legal tender and nobody have to accept any bitcoin - with normal dollar any dollar is a dollar that is worth always the same and cannot be legally tainted with crime. It's more legal question that a technical one because government could not adhere to technology reasons.