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.