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.
The #appengine channel on Freenode is a pretty good place to ask. There are oftentimes people from Google who are working on GAE and can help you out.
Worked for me several times.
I still don't get why people keep on talking about how awesome App Engine deployment is.
It's painless and fast so why shouldn't it be awesome?