Some MX or DNS issue - we cannot send or receive mail to/from schools.nyc.gov

We have a major client schools.nyc.gov and all of the sudden we cannot send or receive email with them.  It started this weekend and I received reports from my users on my domain saying that email TO schools.nyc.gov were bouncing.  (I am new here and still figuring out the systems)

I thought that this problem was our FirstClass email server so I called tech support and he told me that the log below shows that it's on the schools.nyc.gov side.

Anyway please read the rest but I need some clue as to where to look and what to do.   I have called the schools.nyc.gov helpdesk and they brushed me off.  They finally put in a ticket but I feel like they aren't taking it seriously and they think it's on my side.  I'm not even sure at this point.

I investigated this and got this log out of our POS mail server FirstClass:

[2008/10/21 08:07:18] SMTPMsg-34: Processing message 10/475
[2008/10/21 08:07:19] SMTPMsg-34: Relay smtp1.nycenet.edu (0xa59b6865) serves domain schools.nyc.gov
[2008/10/21 08:07:19] SMTPMsg-34: Delivering message to schools.nyc.gov (0xa59b6865)
[2008/10/21 08:07:35] SMTPMsg-34: Rcv: 220 op0iron01.schools.nyc.gov ESMTP
[2008/10/21 08:07:35] SMTPMsg-34: Snd: EHLO mbeabbs.mathsolutions.com
[2008/10/21 08:07:35] SMTPMsg-34: Rcv: 250-op0iron01.schools.nyc.gov
[2008/10/21 08:07:35] SMTPMsg-34: Rcv: 250-8BITMIME
[2008/10/21 08:07:35] SMTPMsg-34: Rcv: 250 SIZE 10485760
[2008/10/21 08:07:35] SMTPMsg-34: Snd: MAIL FROM:<[ mailto:cchambers@mathsolutions.com ]cchambers@mathsolutions.com> SIZE=3070
[2008/10/21 08:07:50] SMTPMsg-34: Rcv: 451 #4.1.8 Domain of sender address <[ mailto:cchambers@mathsolutions.com ]cchambers@mathsolutions.com> does not resolve
[2008/10/21 08:07:50] SMTPMsg-34: Snd: QUIT
[2008/10/21 08:07:50] SMTPMsg-34: Looking for additional mail exchangers
[2008/10/21 08:07:50] SMTPMsg-34: Found relay smtpout.nycenet.edu (0xa59b69fe) for domain schools.nyc.gov
[2008/10/21 08:07:50] SMTPMsg-34: Delivering message to schools.nyc.gov (0xa59b69fe)
[2008/10/21 08:08:06] SMTPMsg-34: Rcv: 220 op0iron02.schools.nyc.gov ESMTP
[2008/10/21 08:08:06] SMTPMsg-34: Snd: EHLO mbeabbs.mathsolutions.com
[2008/10/21 08:08:06] SMTPMsg-34: Rcv: 250-op0iron02.schools.nyc.gov
[2008/10/21 08:08:06] SMTPMsg-34: Rcv: 250-8BITMIME
[2008/10/21 08:08:06] SMTPMsg-34: Rcv: 250 SIZE 10485760
[2008/10/21 08:08:06] SMTPMsg-34: Snd: MAIL FROM:<[ mailto:cchambers@mathsolutions.com ]cchambers@mathsolutions.com> SIZE=3070
[2008/10/21 08:08:21] SMTPMsg-34: Rcv: 451 #4.1.8 Domain of sender address <[ mailto:cchambers@mathsolutions.com ]cchambers@mathsolutions.com> does not resolve
[2008/10/21 08:08:21] SMTPMsg-34: Snd: QUIT
[2008/10/21 08:08:21] SMTPMsg-34: Looking for additional mail exchangers
[2008/10/21 08:08:21] SMTPMsg-34: No additional mail exchangers found, delaying recipients
[2008/10/21 08:08:21] SMTPMsg-34: Delaying recipient "JHugule@schools.nyc.gov"
[2008/10/21 08:08:21] SMTPMsg-34: Updating message history Who="JHugule@schools.nyc.gov" When=-987545995 What=22
[2008/10/21 08:08:21] SMTPMsg-34: Done processing message

So it looks like to me that they are looking up our domain and saying it's not resolving correctly.

I then looked up our MX records and they are correct :

0      mbeabbs.mathsolutions.com      216.31.244.162            
15      groups.mathsolutions.com      216.31.244.162                  
20      caseyjones.dundee.net      216.234.106.37                  
30      caseyjones.dundee.net      216.234.106.37            
40      mail.mathsolutions.com      64.151.115.12      

Our mail comes into Spamassassin then Postfix and then into FirstClass.  

Then the plot thickens because I get a call from a user on the schools.nyc.gov network and they are trying to send us email and it's bouncing as well.  I asked her to forward me the bounce messages and this is what she is getting:

From:   System Administrator
Sent:   Tuesday, October 21, 2008 8:37 PM
To:     nrizzo@mathsolutions.com
Subject:        Undeliverable: Summer Geometry course

Your message did not reach some or all of the intended recipients.

      Subject:  Summer Geometry course
      Sent:     10/19/2008 8:07 PM

The following recipient(s) could not be reached:

      nrizzo@mathsolutions.com on 10/21/2008 8:37 PM
            The e-mail system was unable to deliver the message, but did not report a specific reason.  Check the address and try again.  If it still fails, contact your system administrator.

            < schools.nyc.gov #5.0.0 smtp; 5.4.7 - Delivery expired (message too old) 'DNS Soft Error looking up mathsolutions.com (MX) while asking recursive_nameserver0.parent. Error was: unable to reach nameserver on any valid IP' (delivery attempts: 0)>