Mail is not leaving mail queue

We moved our server into the DMZ zone of the network and opened it up to the outside world, since then we are having problems getting all of the mail to send.

From JIRA we are able to send test messages that go through just fine. Users are receiving messages about password changes, and occasionaly users will receive ticket updates through email.

Under the mail queue link on the admin page, the mail queue tab will have, lets just say 20 mails in it. After about 15-30 minutes all the mail in the queue will slowly leave the queue, then it will all re-appear (highlighted in pink) along with new mails. This process will repeat indefineatly.

SMTP communications from the server have been tested from command line smtp commands to both internal and external clients. Test messages sent from JIRA to internal and external clients work. But when JIRA generates a message about ticket updates or changes to send to issue watchers, they do not get sent out, just keep getting repopulate in the mail queue highlighted in pink.

Any thoughts?