The flaw (or feature) in the current design is that the session entries are cleared as soon as they expire. So if a user tries to continue with an expired session id,...

Consider this ID as invalid and indeed expired, then authenticate him/her again to generate a new session ID.

About the only thing I think I can do at this point is penalty box the user id after a failed login.

But consider a threshold, a number of tries before taking punitive action, a user might mistakenly enter his/her password quite repeatedly with no malicious intent at all, and you don't want to tick a user off at this sesnsitive time.