Your network sounds like a bit of a mare. If traffic to port 25 is permitted outbound you can put this line into the cmd in windows to test it:
telnet cluster4.eu.messagelabs.com 25
If you get a message like this: 220 server-2.tower-182.messagelabs.com ESMTP
That means SMTP is allowed outbound.
If you get: Connecting To cluster4.eu.messagelabs.com...Could not open connection to the host, on port 25: Connect failed
SMTP is blocked
If you get something about unrecognised commands, you need to turn telnet on.
Enable telnet by going to control panel > windows features > then tick the telnet client
To check any other outbound port, use the address of a server you know definitely listens on that port, and cut the 25 off the end of that line and put in whatever number you need. This is a very basic way of testing a given port - it doesn't work at all for UDP ports, and sometimes you get odd results. But for mail service testing it should be fine for you.