That is the key point - escalate past the front line.
The front line is limited in what they can do by the pre-programmed response function keys.
You will have to escalate high enough up the food chain to reach someone who's job description allows them to think for themselves.
At the very minimum, you have to get transferred out of the "Customer is always wrong" department.