It's a bit tricky, since "this call may be recorded" often is played only to you before connecting to the other person, so technically this announcement was not made to them.
Their line helpfully tells you in advance "this call may be recorded." Great! Looks like permission to me! Record I shall! If they object to the call's being recorded, they ought to take that up with whomever controls their phone lines.
If you're calling a corporation (or they called you) then it's the corporation that's the legal entity being recorded... Not the person on the other end of the phone.
People have separate rights even if they are employees, and wiretapping laws apply to recording people - like, the company recording their own calls can easily be a violation of wiretapping laws if they don't properly inform their employees.