The problem with adding tombstones to a schema is that they infect every join and you must manually cascade the delete in related tables. For simple schemas, like a blog or simple cms it is manageable but it gets hairy as your schemas get more complex.
This is 100% accurate. In some cases you can't use a unique on a column because of the "deleted" boolean or a state machine that is in a deleted state. I would venture to guess that this is where a NoSQL solution would come in handy. Just grab all the data they deleted, shove it into a nice json or xml data structure and store it in the nosql database as a document.
