I already solved this issue but it was such a pain in the arse I thought I would post my problem and results just in case anyone else has the same issue.
Our network connectivity took a dive and we had to switch over to our redundant circuit. Unfortunately it is on an entirely different block of IP's (not really sure that was one of the issues in the chain though).
After changing the IP and sending Zimbra back to the outside world the MTA would not deliver mail and get the error: Connection to server timed out (port 25).
DNS lookup for the MTA is not running. Thus the MTA is looking at the address of the recipient (i.e. - the domain name) and not the MX record for the recipient. So it is attempting to deliver to the domain name which obviously does utilize port 25.
Here is what to do:
Confirm whether or not DNS lookup for the MTA is running:
This will return:
su - zimbra
(....zimbra services stop....)
zmprov gs yourservername.com | grep dns -i
If it says TRUE then this isn't your problem.
Now activate DNS for your MTA (watch the case sensitivity).
You may or may not need to reboot.
zmprov ms yourservername.com | zimbraMtaDnsLookupEnable TRUE
And there you go. You should see your mail queue flush and the error go away.
Hope this helps some poor schlump out there that is pulling his hair out as much as I was.