Does the table constraint CHECK gets executed on deletions?
Have you tried ON DELETE RESTRICT ? You can combine this constraint with a function attached to the foreign tables CREATE TRIGGER ON DELETE

CREATE TABLE my_table (
  foreign_key_id uuid REFERENCES my_foreign_table ON DELETE RESTRICT
);

CREATE OR REPLACE FUNCTION foreign_object_delete()
RETURNS TRIGGER AS $$
BEGIN
    DELETE FROM my_table 
    WHERE foreign_key_id IS NULL 
    AND foreign_key_id = OLD.foreign_key_id;
    RETURN OLD;
END;
$$ LANGUAGE plpgsql;

CREATE TRIGGER foreign_row_trigger BEFORE DELETE ON my_foreign_table 
    FOR EACH ROW EXECUTE PROCEDURE foreign_object_delete();


Update:
Check a condition in several tables before deleting the record

CREATE OR REPLACE FUNCTION foreign_object_delete()
RETURNS TRIGGER AS $$
BEGIN
   IF SELECT exists(SELECT 1 FROM table_x WHERE column_x = 'SAMPLE') THEN
      DELETE FROM my_table 
      WHERE foreign_key_id IS NULL 
      AND foreign_key_id = OLD.foreign_key_id;
   END IF;
      RETURN OLD;
END;
$$ LANGUAGE plpgsql;