I've always wondered if "this call may be recorded" messages could be legally interpreted as them giving you permission to record the call, since you-know, they told you it may be recorded.
I remember it as a matter of consent and most resources point to it being OK as long we both parties are aware.
e.g. http://www.dmlp.org/legal-guide/recording-phone-calls-and-co...