I've experienced similar problems, although it might have been the other way around with incoming working and outgoing not. I'm afraid I dont' remember the details but what created the problems for me seemed to be that I was using a BT server for incoming/outgoing, which worked fine while I was connected to the internet through BT but not when traveling and using other ISPs. Some kind of authentication issue I guess. Haven't had an of those problems though since I switched to gmail (which I got set up with Mail as well).
Might be useful knowing what your settings are, especially for authentication?