There is a hack of sorts. You create a duplicate of the primary key column, named e.g. id_active. You create a CHECK constraint which says something like "(status = 'Deleted' AND id_Active IS NULL) OR (status <> 'Deleted' AND id_active = id)". You create a unique index on "id_active", and point your foreign key to that. When you create a record, populate both id and id_active to same value; when you soft-delete it, set id_active to NULL. Actually, maybe a simpler solution is to make id_active a "GENERATED ALWAYS AS ... STORED" column–although I'm not sure if Postgres supports them for foreign keys? That's a relatively new Postgres feature and I haven't done much yet with the more recent versions in which that feature was added.
As an aside, they’re a great feature. We’re using them to generate columns that we can index for efficient joins between tables and also for creating text strings for searching over using trigram indexes. The whole thing is really seamless.
It was one of the many things that impressed me so much when I was a user that made me want to hack on the tool for a living.
So, this problem of soft-deletes becomes trivial