Is is possible to rebuild wp_term_relationships table?

If your AUTO_INCREMENT value wasn’t reset and your new posts will still have unique IDs and you can do:

SELECT tr.*, p.ID
FROM wp_term_relationships AS tr
    LEFT JOIN wp_posts AS p ON tr.object_id = p.ID
WHERE p.ID is NULL;

to see which term relationships are orphans and use a DELETE FROM to fix it.