Tombstone Table vs Deleted Flag in database syncronization & soft-delete scenarios
In general it is better to know the specific requirements and not make design decisions based on what works best in most situations.  Either could be preferable.  Here are some specifics to gather:


How fast do deletes need to be?  
How fast do un-deletes need to be?
How often will deleted data be queried and will it be queried with data that has not been deleted?
How fast do queries of deleted data need to be?
Do you need to preserve only deleted items or changes as well?
Do you need to keep the table/indexes on the primary table small?
What partitioning and/or change tracking technologies are available on the database platform?
How much disk space is available?
Will the deleting occur on the fly or in batch operations?