Как лучше делать проверку при добавлении данных в mysql?
Добавьте поле `updated` TINYINT(1), добавьте UNIQUE KEY (`user_id`, `obj_id`).
Перед изменением сбрасываем отметку:UPDATE `table` SET `updated` = 0 WHERE `user_id` = $uid
При изменении отмечаем добавленные/дублированные записи:INSERT INTO `table` (`user_id`, `obj_id`, `updated`) VALUES ($uid, $oid, 1)
    ON DUPLICATE KEY UPDATE `updated` = 1
После изменения удаляем неотмеченные записи:DELETE FROM `table` WHERE `user_id` = $uid AND `updated` = 0
У меня есть схожая ситуация со связующей таблицей категорий. 
Лично мой вариант - удалять и записывать заново, в первом варианте уйдет больше ресурсов, что не совсем хорошо