1) I'm able to ping the mail server on both our admin nodes.
2) Mail server can be resolved by DNS.
3) Subnet that the Admin nodes are on have been added to the "trusted hosts" by our Exchange Admins.
I did try to telnet using port 25 into the mail server and this is the error I get:
Connected to <mail server>.
Escape character is '^]'.
421 4.3.2 Service not available
Connection closed by foreign host.