I'm not a GAE expert, but using the GAE memcache clone wouldn't be a good idea in this case? The low latency requirement should be met and it looks like that his data structure would fit well in a k/v store.
I've been using AppEngine for almost a year. It's definitely come a long way, but it does still have some serious shortcomings. Most notably is support. If they could offer a level of professional support to organizations willing to pay, I would both pay whatever they wanted and would no longer have anything to complain about. AppEngine is a great product and watching it mature is fun, but frustrating at times.
