Well the approach we have taken is an FK-based one. (Previously, we had used triggers.)

We have a calculated column on the parent table which is normally equal to the PK, but equal to minus the PK if the record is deleted. (So it remains unique and not null.)

And we have a calculated column on the child table which is normally equal to the ParentID, but equal to null of the record is deleted.

Then we have a FK from the calculated column on the child table to the calculated column on the parent table. This allows all combinations of deleted on both tables with the exception of having a deleted parent record but an undeleted child record - which is exactly the validation we require.

(This approach also needs a unique index on the calculated column on the parent table. We also have one on the calculated column on the child table for performance.)

It seems to work, but it does seem a bit of a palaver. So I was wondering if there was a better (i.e. simpler) approach. Perhaps not!