I was interested to chase up what the actual law is here in Oz. And of course it is a mess.
Phone calls are covered by federal legislation, and you cannot record anything off the phone system until you have the agreement of the other party. This covers wire taps and like as well. Any communication that at any time runs over the telecoms infrastructure is covered. A purely radio based conversation isn’t, but a hybrid is.
However, once the audio is off the phone systems, that law don’t apply anymore, and we revert to state based laws about recording of conversations in general. So if you record a conversation from a speaker phone you are under state control. (Or even recording with your phone seems OK. Just not off the phone wires.) States differ. Many just require notification. Once you know it may be recorded it is up to you to terminate or not. However notification must occur prior to the recording starting. Some allow recording if the other part doesn’t know, so long as the recording isn’t shared with anyone (other than the person recorded) and most provide exemptions for protection of legal rights. So here, I suspect, that if you record a conversation with a company you are having a legal wrangle with, you don’t need to get their permission or even notify them, and could use it as evidence. But you sure as heck can’t release it to the media. Safety critical uses are also exempt. Emergency services record all calls, as do many sensitive entities.
Here, the recorded message “may be recorded…” is notification that that a recording may occur. It is neither giving or seeking permission, as permission is not needed. So it is unidirectional. If you want to make an unencumbered recording you have to tell them that you are going to. They can proceed with the call or not at their choice.