If I phone in to a call centre and get an automated message saying that "the call may be recorded", then I would take that as permission to record the call. Although I expect that the message is supposed to notify me that the other party intends to record it, it cuts both ways.