These companies know that worker bee call center drones say things all the time that the company doesn't want preserved in a court of law later- mainly promises that the company doesn't want to have to uphold if they were outside policy. They take it very seriously. I suspect any major company with something to lose has a similar policy.
In the US it's either one party (the majority of states) or all party.
What I do is I inform and get consent from hotline agents during the call.
If a business states that the call may be recorded, then they are already consenting. Therefore your recording would be the 2nd party consenting.
"Determining which jurisdiction’s law controls in cases involving recording devices or parties in multiple states can be complex, so it is likely best to adhere to the strictest applicable law when in doubt, and/or get the clear consent of all parties before recording."
So it doesn't seem to be simple to determine what's legal in any given situation.