> However, if I tell the company I want to record them, they have very little reason to humor me. In practice, this means I'm almost always being recorded anyway, but I can't generally record them back.

I’m pretty sure you’re allowed to record calls if a company plays that message. It’s implicit that if they are notifying you the call is being recorded, that they are also aware and agree to being recorded.