Если нет проблем с производительностью TRUNCATE,INSERT, то не стоит и загоняться.

Если объем данных большой, а изменяются они мало, то оптимальным вариантом было бы добавление в xml поля «версия», «временная метка» и т.п., дабы было максимально просто отслеживать изменения. Также в отдельном файле стоило бы хранить список удалённых записей.

Если очень не хочется делать TRUNCATE напишите хранимую процедуру INSERT_OR_UPDATE, которая будет либо добавлять запись либо обновлять её. Firebird например умеет INSERT OR UPDATE из коробки.

Если не вести журнал удалённых записей, то задача всё равно сведётся к проверке «Если записи нет в xml, то удалить её из базы», для всех записей в базе.