Every one of your questions has straightforward answers:
> How do you determine what coins have been through a mixer?
By looking at tx inputs and going back all the way to when those coins were mined into existence?
Graph the blockchain. This isn't a new idea. There are several visualizations that have already popped up showing who is sending coins to who. Mixers show up as a giant tumbleweed shape in these.
> What if an innocent wallet happens to receive "dirty" coins even when the wallet holder themselves has done nothing wrong?
For one, you'd need to send them a massive amount of money to taint their stash. For two, simply send back the coins to clear your name. The point is that it's relatively easy to detect when an account is receiving coins primarily from a mixer.
> Who would be in the charge of enforcing this? The network? The exchanges?
The exchanges.
> If this is done at the exchange-level, what's stopping someone from simply cashing out via Amazon gift cards or the like through a non-traditional exchange service?
The price of mixed coins will plummet if exchanges refuse to deal with them. Remember "GoxCoins"? Same thing. Non-traditional avenues aren't an escape from these forces when everyone agrees they're relatively worthless.
All in all, the above proposal is no more difficult than implementing the fraud detection prevalent in most financial companies. I'm pretty sure people are being evasive solely because they don't like the idea, not because it's difficult. It seems like a bad idea to refuse to take it seriously.