hello,
We had a similar problem but that was caused by our upsteam DNS servers (running an outdated version of Bind).
We had the problem with all mail targeted to Sweden and where able to work around it by making an DNS exception rule that queried one of the .SE root servers directly for all .SE mail.
We are lucky enough to have brand new DNS servers in place now and that completely solved the problem for us.
Hope this helps!
Steven