Honestly I always take "This call may be recorded" as two way consent :) one time someone was referring to person with hard to pronounce name and I said "that's fine I will play it back". Person responded: "wait, are you recording? I didn't give you my consent". To which I said yes you did, when I called your line answered with announcement that this call can be recorded. He wasn't too happy :)
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.
