I used to have the same problem, and the port 587 trick didn't work all the time for me.

This is more than you probably wanted to know about what's going on.

I got tired of changing my SMTP settings every time I got to a new hotel, so I found this:

http://www.authsmtp.com/auth-smtp/overview.html

It costs a couple of bucks a month. Never had an issue since, anywhere in the world.