Yeah, "this call may be recorded" could hypothetically mean two different things, but it can't mean both of them at the same time. Either the statement means, the company you've called is giving you permission to record the call. "You may record the call if you so please." Or the statement means, "It is possible that we may be recording the call." From the context it's clear that the statement is intended to mean the latter. You're playing a linguistic game to have it both ways. People don't grant permission through puns and double entendres.

Also, those messages about calls being recording don't simply say "this call may be recorded." You've taken the statement out of context. They pretty much always say something to the effect of "this call may be recorded for quality assurance and training purposes." Do you think that the company you've called is granting you permission to record the call for your own quality assurance and training purposes? It's obvious that the statement is referring to the company's own call recording practices in their call center, not to giving you permission to do something.

What's more, what the law says is that the person recording the call must notify the other party that they are doing so. So even if the other party without prompting said that they were giving you permission to record the call if you wanted to, that still wouldn't be enough. It doesn't matter if they grant permission, before you say anything. What the law requires is that you explicitly notify the other party that you're recording the call.

Basically it just seems like you want an excuse not to have to tell the other party that you're recording the call.