there was already some sort of expiration time - a session key from 2 months ago wasn't valid. Expiring the keys to coincide with aged/invalid sessions would have been 'good enough'.
No.... forget that, it wouldn't. It would have been better, but not good enough.
Having something that is an understandable identifier in the cookie is just bad. Crack the key, and when the identifier is 187644, and the next one two minutes later is 187663, you can pretty much guess how to take over accounts. Crack the key when the identifier is qo8GbwieYKK7d3hs92ujvn65CgD and you are pretty dead in the water without brute forcing. This is the point I was trying to make to them, and what I got back was variations on 'random isn't really random'. Somehow identifiers 187644 followed by 187645 seemed infinitely more secure than qo8GbwieYKK7d3hs92ujvn65CgD followed by 7f6Dhj23CNHS8927gfodop289jz because of an encryption key - that never got changed.
Those points on the tech aren't as important as the people issues. I have been through what you describe so often and so many times, very familiar situation
which is why I assume they didn't want to update the key either, since it would invalidate every session