I will attempt this over the weekend when there aren't as many employees in the office.
For reference: we're using a Watchguard Firebox as our Internet Gateway/Firewall. It also splits the connection coming in between the mail server and the office network (the mail server does not reside on the network itself).
The reason I believe the issue is not being caused by the firewall is two fold:
1) Prior to this, we had a switch and a router filling the role that the Firebox fills now and still had this issue come up.
2) The configuration in the Firebox's settings for SMTP (port 25) traffic is identical to the configuration for POP3 (port 110) traffic and POP3 traffic does work outside of the office.
But definitely will try to access without the firewall in place this weekend and will report back.