Just found http://plugbucket.net, they look pretty cool. No weird TOS restrictions, and the flat shipping to anywhere in the world is pretty nice as well. $9/mo with a $150 initial purchase fee or $22/mo with nothing extra upfront.

They're debian 6 boxes, with 100mbps bandwidth and 512mb ram; only downside is all additional storage (besides the 512mb onboard) is mounted over NFS.

Just ordered one, can't wait to play with it