Recently I had the strange problem. In an old Magento installation there where many simple products connected to parent-ids that didn’t exist anymore. Normally that should’t be possible because of foreign key constraints in MySQL but  in fact they where there. Perhaps there was a bug in an importer script or foreign key checks where disabled somewhere in the past – I had no idea -. So I had to find and eliminate dead parent connections.
I solved this by running the following queries directly on the database:

# Lookup dead related connections:
SELECT cpr.*, cpe.entity_id FROM catalog_product_relation AS cpr
  LEFT JOIN catalog_product_entity AS cpe ON cpr.parent_id = cpe.entity_id
WHERE cpe.entity_id IS NULL;

# Delete dead related connections:
DELETE cpr.* FROM catalog_product_relation AS cpr
  LEFT JOIN catalog_product_entity AS cpe ON cpr.parent_id = cpe.entity_id
WHERE cpe.entity_id IS NULL;

# Lookup dead superlink connections:
SELECT cpsl.*, cpe.entity_id FROM catalog_product_super_link AS cpsl
  LEFT JOIN catalog_product_entity AS cpe ON cpsl.parent_id = cpe.entity_id
WHERE cpe.entity_id IS NULL;

# Delete dead superlink connections:
DELETE cpsl.* FROM catalog_product_super_link AS cpsl
  LEFT JOIN catalog_product_entity AS cpe ON cpsl.parent_id = cpe.entity_id
WHERE cpe.entity_id IS NULL

To protect my own live 😀 I decided to simulate this first, with the help of a MySQL-Transaction, before running it on production system. 😉