There are benefits for marking a row as deleted w/ a boolean column though. Undo-ing deletes would be easy to implement, and retaining references to deleted records would be simple as well.
The solution the problem you described would be to use a surrogate key column (typically a UUID/auto-increment), and not natural keys.
The solution the problem you described would be to use a surrogate key column (typically a UUID/auto-increment), and not natural keys.