Re: re. recording calls
In the UK there is no prohibition on recording calls, as long as *one* of the parties on the call knows (designed to cover phone-tapping).
It's my understanding that it's the same in the US. To me, the message to the customer that the call may be recorded indicates that the agent is the one who is not aware that the particular conversation is being recording.
Also, it may be a public-relations thing rather than a legal thing.