You can do it with software. It is merely a chain of TX's.
One wonders how quickly wallet theft would disappear, if the other major exchanges started rejecting well known, stolen coins.
That is one very big slippery slope.
VERY big and slippery.
For example, someone recently wanted to know if they had any coins from the famous 10000 btc pizza sale:
http://bitcoin.stackexchange.com/questions/450/is-there-any-way-to-track-an-individual-bitcoin-or-satoshiTurns out 29% of currently operating bitcoin addresses contain a little pizzacoin magic:
As of block 166149, on Feb 10th 2012, 1,037,382 addresses have held the pizza coins since they were spent. 174,584 of those still hold pizza coins (the others may or may not be empty addresses, since it's possible to have two different transactions output to the same address without the coins becoming mixed together. In other words it's possible to have "pizza coins" and "non pizza coins" in the same address and still be able to tell which are which. Of the approximately 600k addresses which are currently holding funds, around 29% of them contain pizza coins.
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.