Thanks for the reply Alfred. Sorry for the delayed response. I'm only able to work on this on the weekend and I spent all last weekend porting to a different framework to debug the problem.
TL;DR - Despite crashing more often than not, I could never identify where the keyless encoded entities were being created.
My app was last deployed around Thanksgiving 2010 using whatever was the then current sdk. It was created on top of the Kay framework. When I installed the latest SDK (to get this code breaking change), Kay spit out errors. Even after I upgraded to the latest Kay release the dev appserver still wouldn't run. So I couldn't reproduce the problem in an environment where I could dig in to the entities causing the crash.
On the production servers, I could track down that the problems were from decoding memcache'd entities. But since you can't browse the memcache entries (like the datastore) without knowing specific keys, I couldn't dig very deep there either.
Finally I gave up and started porting my app off of Kay and on to the latest webob & webapp2 releases that still support python 2.5. When I was able to redeploy on that foundation, the problem disappeared. I was pretty aggravated to have my app crashy for so long and then to lose a weekend to porting it, but at least the update has gotten me 75% of the way towards getting the app ported to the 2.7 runtime.
Thanks again for the reply with the source link. If the problem rears it's head again I'll be better prepared to know where to look.
Regards,
Steve