domain not found

[Martin S]

We are experiencing something weird in our DNS server(-s).

Users are reporting that they can't mail to some domains, among them
hotmail.com. However doing:

dig @212.209.75.120 mx hotmail.com

brings up a long list of mail server. And I can do

uname -a | mail -v -sTest user at hotmail.com 

from the DNS server and get through to the mx server on hotmail.

FUBAR at hotmail.com... Connecting to mx1.hotmail.com. via esmtp...
220 mc9-f7.bay6.hotmail.com Microsoft ESMTP MAIL Service, Version:
5.0.2195.5600 ready at  Fri, 22 Nov 2002 04:21:42 -0800 
>>> EHLO stigfinnaren.forumsyd.se
250-mc9-f7.bay6.hotmail.com (02.00.05.0005) Hello [195.242.49.154]
250-SIZE 3565158
250-PIPELINING
250-8bitmime
250-BINARYMIME
250-CHUNKING
250-VRFY
250-AUTH LOGIN
250-AUTH=LOGIN
250-X-HMAUTH
250 OK
>>> MAIL From:<root at stigfinnaren.forumsyd.se> SIZE=131
250 root at stigfinnaren.forumsyd.se....Sender OK


etc


However, when sending mail from our mail server using our DNS server
mail to trouble domains (incl hotmail.com) bounce with the following
error (First Class server):


Sorry. Your message could not be delivered to:

hotmail.com
	(domain name not found)


After 30 min. on support with UUnet the problem seems to be on our
end. But I can't seems to understand where.
Any suggestions?

/M.