Обратите внимание на другой ответ относительно индексации. NOT EXISTS обычно довольно быстрый, если у вас хорошие индексы.
Но у меня были проблемы с производительностью с утверждениями, которые вы описываете. Один из методов, который я использовал для обхода, состоит в том, чтобы использовать временную таблицу для значений-кандидатов, выполнить DELETE FROM ... WHERE EXISTS (...), а затем вслепую вставить остаток. Внутри сделки, конечно же, чтобы избежать условий гонки. Разделение запросов иногда позволяет оптимизатору выполнять свою работу, не путаясь.