May be we should add a counter to expire cache values, so the exceptions don't invalidate a value completely? Especially in the case of a new user, you'll try to get his key, fail with an exception, create one, and then try to get it again (to which you'll get the same exception, haven't tested this though). So... now that I re read this, a counter is not good enough.

If it fails, and then fails 20 times over because whatever reason, I think that's what should happen, even if that delays the process.