For foreign key constraints you can set the foreign key to null and orphan the records if the relation is deleted. You could also hard delete them in this case. It depend on your use case.
When the data volume grows or the ratio of soft deleted to normal records is high, you should consider another solution. One solution you suggested, moving the record to a deleted table is a fine one.
The other solution that I've used successfully is to journal your deletions in another table or system. For smaller volumes having an audit table Journaling the data and storing the pk, fkeys, and a serialized version of the record, json works great in postgres, works well. For large volumes or frequent deletions something like Kafka or PubSub work better.
You may very well find others interested in consuming your audit journal to track changes. Updates and even inserts fit great in the more general case.