On this case, one way is to make a past_ or deleted_$tablename where you insert the deleted row before deleting it from production table.

This way you can watch post mortem, restore etc...

AND it's not soft delete since the data is really gone from the production table, therefore no query tweaking

Only thing: you need to really delete when GDPR related deletion is requested.