The last used PK for a given table is stored in a special table called AUTO_PK_SUPPORT. Please check the contents of this table between the restarts of your app. Also check you application Cayenne logs for reads and writes to AUTO_PK_SUPPORT. This should give you an idea of what's happening.
Aside from that you might switch to auto-increment PK (see "Primary Key Provided by Database" section here). MySQL supports auto-incremented PK columns and if you have an option of altering the schema, this IMO is the cleanest PK generation strategy out of all available. (And it doesn't require AUTO_PK_SUPPORT).