Т.к. MS Access по сути файл-сервер, то быстрее тащить на клиента всю таблицу и сравнивать клиентом.

Т.е. допустим у тебя ключ из трех полей f1,f2,f3
список новых подготавливаешь в памяти и сортируешь по (f1,f2,f3)
затем select f1,f2,f3 from MyTable order by f1,f2,f3

Дальше в один проход сравниваются оба набора. В результате получишь список того что надо добавить.

Для ускорения сравнений можно добавить поле с CRC32 записи. Получишь 32-битный почти уникальный хэш ключа. Считается быстро.
Тогда если CRC32 новой записи отсутствует - это однозначно скажет что запись новая, иначе досравнивать f1,f2,f3. Также сортировка и выборка по CRC32 будет быстрее чем по (f1,f2,f3)