Could you easily move out of GAE? I made a site on that platform a couple years ago for fun, and would get anxious every time I'd get an email from them with terms of service or API changes.
Not too easy, but not as hard as people expect either. The App Engine SDK is open sourced. This is the layer that connects your code to Google's infrastructure. There are a couple of projects that have taken that SDK and modified it to connect to MySQL, MongoDB, memcached, and so on. They allow you to run your GAE app on your own server, without changing your code. I tried typhoonAE a while ago and managed to get my app running on another server with about a day of work.