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.