I have heard that stolen bitcoins are not allowed to process further in the blockchain, i.e. they are rejected.
This is not true at all. Somebody made fun from You.
Are there bitcoin based businesses out there that reject stolen bitcoins? Are they like blackmarked?
Some businesses are known in some time in past to keep and not release coins they consider "tainted". Mt.Gox are prime example on this. And there are nolifers who follow transactions down to blockchain wasting their time in a hope to catch the thief.
If You need assistance for properly laundering your coins so they will be accepted as clean by all exchanges then I will do it for very small fee.