Possivelmente sim, mas é mais provável que seja causado por um provedor de spam conhecido do que mudar de país. Faça o que você já deveria estar fazendo hoje - publique registros SPF e não envie spam.
Além disso, faça algumas pesquisas sobre o seu provedor - veja se eles geralmente acabam nas RBLs.