can you ping the mail host IP from your LAN?
Can you access webmail from your LAN?
If so then you need to check your firewall, ensure that all smtp ports are open or forwarded where necessary.
I also suggest that you talk with your ISP the problem could also be coming from there.. Your Public IP could be black listed.
Another problem would be if you have changed your network class lately there are config details in your mailserver set up that you need to update.
So there are many reasons why your mailserver would fail to fetch or send..
Trace your steps first then we can get you a solution as you zero in on something. Right now the reasons are endless..
Regards
Oliver