I would probably stick with the apologetic approach. The rationale being that apologizing once too often will have a far less negative effect than not apologizing when appropriate. IIRC that philosophy was also discussed in Dale Carnegie's "How to win friends and influence people".
I don't know the right answer in this particular case, but I have had long, interesting discussions about this whole thing in the past. A few off the cuff thoughts rooted in those discussions: I think a better goal is to fix the problem, make amends, and avoid having any reason to apologize. Apologies tend to read as admission of guilt. If you don't amend the problem but you keep apologizing every time it happens, you are behaving like a stereotypical abusive spouse. In other words, if apologies without solutions are normal behavior for your company, you are, in fact, guilty and the customer is not really being unreasonable to want to treat you like their bitch.