In the United States and in many other parts of the world, it's quite common for residential broadband connections to have traffic filters preventing access to port 25 on any other server than the broadband provider's. To be clear, this is a very good thing. This prevents people from directly connecting and attempting to deliver spam directly to your email servers. It's most likely that this is the packet filtering you're experiencing while at the coffee shop. I'd suggest you try connecting to other mail servers on port 25. If you can't reach them, then it's most likely the internet provider has that blocked.
Hosts to try would be sncwsrelay1.nai.com and sncwsrelay2.nai.com at McAfee or mail.messaging.microsoft.com at microsoft.
Further, you indicated in the follow up to another answer that your Cisco ASA was configured to accept email from the mxlogic servers. Also, you indicate that no email is sent from the server directly but is instead forwarded via a Smart Host. What does this mean with regards to SPF and reverse DNS?
Well, any SPF records should authorize all the machines that whomever your emailsmarthost you're using has as external smtp servers. Remember, SPF is for advising the world what servers on the internet should be trying to send mail from your domain. Since you're not actually attempting the final delivery of the email yourself - you're sending all your outgoing emails to your smarthost - your SPF records should list all of the smarthost provider's external servers. If you contact them, they should be able to supply you with a list of hosts for inclusion in your SPF record.
With regards to reverse dns, since you're never directly receving or directly sending any email, it should not be an issue.
Also, presumably, you have MX records in DNS that list the mxlogic email servers as the email exchangers for your domain. That's great.
Also, most modern email software requires considerable effort to be configured to operate as an open relay. I'd have someone at mxlogic or your commercial internet provider verify your exchange server's open relay setup. To be honest, though, with a smarthost and assuming the smarthost has reasonable sender address filtering, I would say that you're very likely not an open relay.
Cheers.
Sorry this is so long, I'm waiting for tape backups to finish.