I worked on a database that allowed (almost) every table to mark a row as deleted with a boolean-type column. This caused problems when you wanted to create a new row that had the same values for the table's key-columns as a deleted row. You can't just add the deleted column to the key and have all the functionality you want (multiple deleted rows with the same values in the table's key-columns). Each table could use (or not) the flag in different ways and there was no simple way to enforce consistent behavior across all tables. The constraint has to be placed somewhere else, either in explicit code, or by creating new abstractions inside the database that allow you to represent the actual constraints of your application.
The solution the problem you described would be to use a surrogate key column (typically a UUID/auto-increment), and not natural keys.
All tables had a unique, integer primary key.
However, if you want to enforce a uniqueness constraint across your data [eg. UNIQUE(name, location)], the constraint breaks when you introduce the boolean deleted column [and UNIQUE(name, location, deleted) does not provide the appropriate semantics]. The application semantics must be provided at some other level than SQL column constraints.