Why not use a different encryption key per session and stamp encrypted ids (or whatever info) to the outside word.

This way the DBs can use simple sequence numbers instead of timestamp based IDs.