Я не могу объяснить , почему как таковое, но декодирование строки, полученной из appengine, показывает, что перед вашим ключом стоит '='; и добавленный , а не предварительно добавленный, идентификатор.
>>> key='r-$b*8hglm+858&9t043hlm6-&6-3d3vfc4((7yd0dbrakhvi'
>>> base64.urlsafe_b64decode('PXItJGIqOGhnbG0rODU4Jjl0MDQzaGxtNi0mNi0zZDN2ZmM0KCg3eWQwZGJyYWtodmkxODAwNQ==')
'=r-$b*8hglm+858&9t043hlm6-&6-3d3vfc4((7yd0dbrakhvi18005'
>>> '=' + key + str(18005) == _
True
Вы абсолютно уверены, что использовали один и тот же код на сервере?