You could enforce the constraint with an insert trigger (before allowing insert make sure no undeleted rows match). That is my best suggestion, but perhaps others have something else.