Bit,extreme,sid,but try installing WinPCap
http://www.winpcap.org/ then Ethereal
http://www.ethereal.com/ . Set ethereal to sniff whichever NIC you use to go out and start it. Then start your email client (outlook,right?) you should very briefly see both your password and login shoot out then the direction of where you email starts and ends. See just how far youre going. May give you a better idea as to where the problems lies and needs attention.
Now try sending again and see if its reaching you and being denied(possible router,firewall,filter,problem) or just not reaching you,period,as in,isnt even leaving the server,in which case, they very well may have something going on with their filters.
Additonaly,can you run a trace route and are all the hops up between you and them? or a dns server temp down?