After testing out Checkpoint' VPN client on my Mac, I disconnected from the server, but left the client on. In other words, the icon was still visible in the menu bar.
It seems this can actually block your ability to receive mail from the server if it is in the same domain or possibly the IP range as the internal network which the VPN client covers. It also seems to block the web - even if the pages in question are on the public network.
So even when it is off, it is active in some way. Only by turning it off completely was I able to get connect to the mail server.