На тестовом стенде удалось воспроизвести, локализовать и победить проблему.
На сервере с NAT в разных интерфейсах поднят BGP с разными маршрутизаторами (маршрутизаторы в свою очередь подключены к разным магистральным провайдерам, т.ч. трафик может прийти как с одного интерфейса так и с другого).
На самом сервере с NAT маршрут по умолчанию смотрит только в первый интерфейс.
Так вот. проблемы начинаются, когда трафик приходит в второй интерфейс (куда нет дефолта). Видимо из-за offload сервер пытается ответить в этот же интерфейс, а так как нет маршрута - посылает ARP запрос