1: Encryption isn't magic pixie dust: people can tamper with the ciphertext and fool you. Sometimes they can even mess with the padding and decrypt the entire message.
2: A rule of thumb that falls out of this: never try to decrypt ciphertext that you can't verify is authentic. Consequence: compute the MAC over the ciphertext, not the plaintext, so you don't have to decrypt to check the MAC.
I've done my message format in the past as "{version}{hmac-md5}{ciphertext}". This is suitably secure, to the best of my knowledge. And thanks to the version, it lets me alter the algorithms or keys without service disruption. Once all sessions using it would be expired, the old version can be assumed to be expired.
If the version is not covered by the HMAC, you may be subject to rollback attacks. Compare the SSLv2 and v3 protocols to see what was done to address this.
I'm sorry, I don't get it. For session cookies, the client cannot do any validation of the cookie, so it's a completely different domain.
Also, unlike session cookies, SSLv2 never had a hard expiration date after which it could be unconditionally rejected.
However, I did just realize that for perfect security, there must be a service disruption on change of version. Otherwise you may be upgrading an attacker's forged v1 cookie to v2, if they submit a request before the v1 expiration.
Upgrading cookies is a bad idea. Revoking them and requiring reauthentication is better. See the talk I gave at Google on web crypto where I talk about exactly that situation.
Basically encryption isn't authentication?