Developer's Amazon account (incl. AWS) permanently closed after login from Japan
twitter.com
twitter.com
Here's a free idea, which is probably pretty stupid, to which I've given exactly 0.2s of thought:
Launch a service that validates travel legitimacy through credit card networks. Basically, a transparent and near-instant check that simply asks the CC networks if an account owner is traveling in location X. My card providers always know when I'm traveling, and are quite intelligent about making sure my card always works. When going out of state/country for any length of time exceeding a weekend to an unusual place, I always tell my card providers. Otherwise, they tend to be pretty good at figuring it out when I don't.
This raises a valid concern especially when traveling, it would be good if large web services allowed you to signify your travel intentions.
One idea might be to allow you to whitelist countries you are planning to visit during your travel window.
I do not know how to handle this, but it really needs very serious attention.