Rejecting stolen coins would only affect the first person to attempt to use the coins, not the thief. If the pizzacoin example is anything to go by, coins are redistributed fairly rapidly. If I'd stolen coins and was worried about exchanges not accepting them, I send bitdust to as many addresses as I could an exchange refusing them would have trouble keeping the rule implemented without pissing off innocent civilians.
This is the big problem with blacklisting coins. Imagine if a thief of a major theft threw 1-2k coins at various pools. By the time the pool owners became aware of the problem, there could be hundreds/thousands of pool users who now have coins that originated from the theft. The pool owner could obviously reimburse the party that had coins stolen from them, but that doesn't change the fact that the coins have been distributed to many innocent parties.
There really is no way to blacklist a theft, outside of the original address used to receive the stolen coins. Anything after that carries the risk of innocent users being accused of being thieves.