We could not send mails to some domains, the message is 450 host down. When I try to do dnsstuff check on those domains, this is what I get, is this really normal.

Your 1 MX record is:

10 mx.company.com [TTL=86400] IP=6x.1xx.1xx.1aa [TTL=86400] [IT]
IP=6x.1xx.1xx.1bb [TTL=86400] [IT]
IP=6x.1xx.1xx.1cc [TTL=86400] [IT]
IP=6x.1xx.1xx.1dd [TTL=86400] [IT]
IP=6x.1xx.1xx.1ee [TTL=86400] [IT]
IP=6x.1xx.1xx.1ff [TTL=86400] [IT]

It seems they have one mx record with changing IP addresses. Is this something new for security ?
Then my smtp cannot figure which IP address to use. And I cannot event telnet port 25 on those servers or even ping.
But they claim they can get e-mails from every where apart from my host. I tested and sent and e-mail from yahoo and it was delivered.

This is what I expected if I look at yahoo with dnstuff.

Your 13 MX records are:

1 d.mx.mail.yahoo.com. [TTL=1800] IP= [TTL=1800] [US]
1 e.mx.mail.yahoo.com. [TTL=1800] IP= [TTL=1800] [US]
1 f.mx.mail.yahoo.com. [TTL=1800] IP= [TTL=1800] [US]
1 g.mx.mail.yahoo.com. [TTL=1800] IP= [TTL=1800] [US]
1 h.mx.mail.yahoo.com. [TTL=1800] IP= (No Glue) [TTL=1800] [US]
1 i.mx.mail.yahoo.com. [TTL=1800] IP= (No Glue) [TTL=1800] [US]
1 j.mx.mail.yahoo.com. [TTL=1800] IP= (No Glue) [TTL=1800] [US]
1 k.mx.mail.yahoo.com. [TTL=1800] IP= (No Glue) [TTL=1800] [US]
1 l.mx.mail.yahoo.com. [TTL=1800] IP= (No Glue) [TTL=1800] [US]
1 m.mx.mail.yahoo.com. [TTL=1800] IP= (No Glue) [TTL=1800] [US]
1 a.mx.mail.yahoo.com. [TTL=1800] IP= [TTL=1800] [US]
1 b.mx.mail.yahoo.com. [TTL=1800] IP= [TTL=1800] [US]
1 c.mx.mail.yahoo.com. [TTL=1800] IP= [TTL=1800] [US]