Well, yes. But playing it back to the person you spoke to is legal. As is submitting it to a court in evidence. You couldn't play it to the person's boss, though.
That would almost be better -- it would be kind of insulting to say it at the start of every phone call, but it might get people to get it right the FIRST time :)
Although quite often when you speak to a call centre, you are told that "calls may be recorded" - in absence of further specification about who may record the call, I've always thought that could be taken as an open invitation by either party.