Si su solución es ajax-y, puede mantener el cursor (como una cadena) en una matriz en el lado del cliente en javascript, por lo que no necesita almacenarlo en Memcache.
Cuando los datos se agregan (o se eliminan/cambian), los cursores antiguos no se invalidan. Aún puedes usarlos. En su caso, básicamente representan el primer elemento en una página. Entonces, lo único que podría suceder es que si está en la página 3 de resultados y navegue hacia atrás y adelante, es posible que no vea exactamente las mismas entidades que antes en la página 3.
Por ejemplo, si pasó de la página 2 a la página 3:
- Page 2 (cursor = x2) resultados: [d, e, f, ..., g]
- Page 3 (cursor = x3) resultados: [h, i, j , ...]
Entonces, si se borraron 'e'. Yendo hacia atrás, la página 2 (cursor = x2) ahora mostrará [d, f, ..., g, h], y actualizaremos el cursor x3 ya que cambió (lo revisamos después de cada búsqueda() para la página 2). En adelante, la página 3 ahora tendrá [i, j, ...]
De forma similar, si en lugar de 'e2' se agrega después de 'e', volviendo a la página 2 tendríamos [d, e, e2, f, ...] y x3 se actualiza. Y en adelante, la página 3 contendrá [g, h, i, j, ...]
La única advertencia es que la primera página nunca debe usar un cursor (en caso de que los elementos se agreguen antes del primero), y siempre debe permitir que el usuario "intente" ir a la siguiente página, en caso de que los elementos se agreguen después del último resultado.
Por lo tanto, los números de página no serán muy específicos, pero no pueden ser realmente al tratar con datos paginados que pueden actualizarse. Un truco es no usar números de página, sino etiquetar las páginas como "datos que comienzan con el elemento x" o algo así.
No conozco ninguna implementación, pero debería ser bastante fácil de implementar. La funcionalidad del cursor se describe bastante bien en los documentos: http://code.google.com/appengine/docs/java/datastore/queries.html#Query_Cursors