The recording is not illegal because you've been told it would happen, and by not hanging up, you've agreed to have a conversation that can be recorded.
This was determined in Kearney v. Salomon Smith Barney, Inc. applying the exception of Penal Code 632 that communications are not considered confidential if there is a reasonable expectation that the call ...
No, it’s not illegal
You have been informed that the call will be recorded. If you continue with the call having that knowledge you have consented to the recording. If you don’t consent you can hang up.
If you need to communicate with them and don’t want to be recorded, do it in writing or in person.
The California wiretapping law applies to "confidential communications", where a party has reasonable expectation of privacy. Organizations often have an announcement that you hear when you are on hold announcing that the conversation may be recorded. If you announce that a conversation is being recorded, there is no reasonable expectation of privacy. They ...
If they are recording you, you can record them
Assuming that recording requires two-party consent (not all places do), when they informed you that the call may be recorded, they gave consent to it being recorded (obviously) and you gave consent by not hanging up. The consent requirement has been met so anyone and everyone can record it.
Yes, it's illegal
When party consent states differ, the state with the stricter laws apply.
Not only can criminal charges be brought against you, but there can also be a civil claims for damages.
Recording Phone Calls and Conversations