I've had the same experience though I don't use a special app, just regular audio recorder, as the phone I'm using for the call isn't my mobile. On every occasion that I've mentioned having a recording of terms distinct from what is actually being provided/charged I've received immediate escalation and resolution.

The funniest was with an ISP (who shall remain nameless) who claimed that they didn't have access to their copy of the previous conversation and thus couldn't confirm or honor the supposedly offered price. Once I mentioned that I had a recording the call resolved in about 1.5 minutes.