Донякъде си представям какво точно се случва. От "другата страна" (демек след proxyarp рутера) има друга машина с ИП адрес същия като на уиндоус машината ти. Но там няма такава машина с адрес като на линукс-а ти, затова с него си нямаш проблеми.
В един момент, твоят рутер иска да разбере на какъв мак адрес съответства ип адреса на уиндоуса. Тогава или праща АРП заявки през всички интерфейси, или му се "дава" gratituous отговор от страна на рутера на доставчика ти и той го приема. Като резултат, вместо твоят рутер да осъществява L2 комуникация с уиндоуса, той се опитва да го прави с рутера на провайдъра ти.
Има два начина да се избегне това, първият е както каза VladSun да се набият статични АРП ентрита, това трябва със сигурност да сработи. Другият е да изръчкаш няколко настройки на ядрото по отношение на АРП "поведението", т.е:
echo 2 > /proc/sys/net/ipv4/conf/*/arp_announce
echo 1 > /proc/sys/net/ipv4/conf/*/arp_filter
които контролират дали ядрото трябва да се занимава с АРП "дейности" през всичките си интерфейси или само през тези, които са в същия subnet. Мисля, че и това е вариант също

'>
А всъщност и трети вариант има, да смениш адресите на НАТ-натите машини с някакви за каквито със сигурност знаеш че не се ползват. За това може да се провери лесно с arping, рутера на доставчика ти или ще отговори от тяхно име, или не - при втория вариант вероятно можеш да ползваш адреса без проблем.