Hi,
Could you describe an environment of your installation? Is this Cloud Provider? Have you got a firewall between Plesk and the Internet? Could you connect via telnet from your Plesk to any mail server on the Internet via 25/tcp port? As an example: `telnet smtp.gmail.com 25`