The reason it doesn't clean up when you restart is the shared memory that it uses for storing the cache. You could have a separate cache per process instead. (There's a parameter to control this.) You could also change the module to use something better like Cache::Mmap instead.

If no one logs in for a while and the data expires, the first time someone performs an action on the server it will still have stale data, but at the end of that request it will be cleared. So, you could say something like "if you've changed your password and your new login doesn't work, just try it again and it will."