Windows 7 - Traveler's woe: Outlook won't send email in some locations

I use Microsoft Outlook for my email. When I travel, I can often send and receive email at hotel rooms and public places. Once in a while, though, I have a problem. In such instances, I can usually receive email ok. But when I try to send email it is blocked.
This has happened at some hotels, bed and breakfast places, and when using the public Internet at AMTRAK train stations (and also when I was in the Canadian Rail train station in Quebec City).

Most recently I received the following error message when trying to send an email:

"Task 'myname@mydomain.com - Sending' reported error (0x800CCC80) : 'None of the authentication methods supported by this client are supported by your server.'"

By way of background, I use Earthlink for my ISP, provided through Time Warner Cable, New York. My outgoing mail server: smtpauth.earthlink.net. I have checked "My outgoing server (SMTP) requires authentication" and entered my Earthlink username and password in the appropriate text boxes on Outlook's Outgoing Server tab. All of this is unchanged from when I am in the office.

I have developed two workarounds:
1) Webmail. I use a service such as Gmail or Yahoo, or Earthlink's own webmail site.
2) Verizon's VZaccess. I tether my cell phone to my laptop, using Verizon's tethering data service.

Both of the above workarounds always do the trick. There is a slight inconvenience, though, since emails I send using those methods are not consolidated in my Outlook data files.

I am wondering if there is any fix for the problem?

Hmmm...

Outlook 2007 Error: None of the Authentication Methods Supported By This Client Are Supported By Your Server | The Pursuit Of A Life

I would bet that the problem is that your ISP blocks connections from outside their physical network. The link below leads to troubleshooting information you can use to deal with the problem.

Can’t Send Email?

@Lemur, and wpmann01: Great information! I am not traveling now, so I cannot test the solutions listed on your suggested web sites. However, I have bookmarked them both and will try everything on my next trip. Meanwhile, I am marking this problem solved. At least one of those solutions has to do the trick.