Alan,
The concept of marking a record for deletion is a part of xBase all the way back to dBase II. Other database managers have not implemented the idea and so it is not surprising that you find it strange.
How do I deal with the PK issue, well I ONLY use surrogate PKs, that is fields that have absolutely no meaning other than being the PK for the table. That way I NEVER reuse a PK value so I don't care if the deleted records are there or not.