There are some issues with the idea. Some of them are subtle:
The first thing to realize is that bitcoins do not exist as independent trackable entities, in the system. So there are no individually identifiable bitcoins that you can 'mark'.
Instead, address balances exist. So, you might say, lets just mark the address balance as 'hot'.
This has some merit. It violates what appears to be a design assumption of Bitcoin, which is that bitcoins are meant to be fungible; but it has some merit.
If someone tries to pay you with a transfer from that address full of stolen coins, you can just say "Im not accepting that as valid payment. Take your business elsewhere."
But, what happens when somebody - lets say an anonymous mixer - accepts, say, 100 stolen bitcoins, into an address that has 900 bitcoins already in it.
Now, you have an address with 1000 bitcoins. 10% of these bitcoins are dirty - but which 10%? How do you deal with this scenario? What if someone tries pay you 100 coins from that address? Do you say that transfers from that address are only worth 90% of the value they had before? What if that address goes through a mixer again? You can keep track of percentage 'contamination' but its going to start making things complicated.
If you accept dirty bitcoins, that weren't dirty when you got them (lets say you are a mixer and get a transfer before people realise there has been a theft), what happens? Also, who gets to say which bitcoins are dirty? A centralised authority? That sort of breaks the design goal of fungibility - if you have to ask a central authority whether this is a real bitcoin or not, why not also just have the centralised authority issue them in the first place, and dispense with all the complexity?
I'm not sure whether a marking system would work; there certainly seem to be some reasons its tricky. I've seen discussions about this on the bitcoin forum; plenty of people there who have thought about this a lot.
It seems that the problem now becomes one of reputation management. The diamond markets in New York work entirely by trust (a handshake can seal a $10 million deal), but that's not possible when the community is the world.
A pretty challenge. :)
In real-world cases like this, you generally launder the money through untraceable sources, where they can re-enter the system from anywhere and be 'clean'. You can do something similar in bitcoin, where I think they're called "mixers". I don't know if any automated ones exist, but basically: mix (i.e., melt) a bunch of people's money from addresses A-M in one account, and send the same amount out to (brand-new, anonymous) addresses N-Z.
N-Z are owned by unknown entities, so as long as e.g. X doesn't receive exactly as much money as only D put in, you can't infer ownership. All coins are 'tainted' because the sources can be tracked perfectly (i.e., a marker chemical in gold), but who owns what coin is now lost. Obviously there's more to it, and distributing without losing perfect anonymity is difficult, but it shows the basic problem. Again similar to melting, you can even send # coins to addresses 1-9 over a large period of time, while melting more and more coins into the shared pool, so there's less of a chance of guessing who owns what based on timing.
For example, after the Linode hack the stolen coins were moving around and there were reports, from people who had bought coins from cryptoXchange or had paid with paxum, that mtgox was freezing those deposits because they were connected to the stolen funds.
I'm surprised someone hasn't started a hot-sheet for stolen coins, so that exchanges and individuals can check before accepting them.