I haven't started recording phone calls with companies yet, but when I started thinking about it, I heard "This call may be recorded for quality purposes" as giving me permission to record for quality purposes.
Yes I think it makes sense to consider the caller query to record the call as a tacit authorization for you to record it as well. (At least in my country it's interpreted that way)