If speed was not an issue and you don't mind having to have 3 keys, could you cover all the bases by doing MAC-then-encrypt, then treat that as cleartext and do encrypt-and-MAC on that, and finally treat the result of that as cleartext and do encrypt-then-MAC on that to get the final thing you send?
https://crypto.stackexchange.com/questions/202/should-we-mac...