Exchange Mail not Reaching you?

If you hear about a message like the one below ask if the "queue is frozen".

I had a case of mail not reaching my server. The sending server was an Exchange server. I asked the admin to check his queue. He had several messages that didn't make it for two weeks and his users didn't get any warning (my servers send warnings after 12 hours and return the message after 2 days). He read me the message below. When I heard the the destination server it made me think of my spam filter dropping connections, but I didn't have any logs of that. Turns out the other admin of the Exchange server had frozen the queue and he didn't know. Upon unfreezing it all of the mail went through. I think this queue freezing feature should at least warn the users of his server.

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

Subject: RE: test message

Sent: 1/26/2009 2:54 PM

The following recipient(s) could not be reached:

me@my-domain.com on 1/27/2009 9:02 AM

This message was rejected due to the current administrative policy by the destination server. 
Please retry at a later time. If that fails, contact your system administrator.