"Ugh, I knowwww. It's totally inconvenient. You might want to consider just bringing your own bag next time. I know, that's sometimes inconvenient, too, but it's better than paying for a new bag each time, right?"
I worked in the hospitality industry for a long time, and a lot of the training I received said to sympathize with the complainer using statements like, "Oh, gosh, yeah, I can see why that would cause you trouble/concern/annoyance." Of course I'm just paraphrasing here, I'm pretty sure that wasn't the wording I was instructed to use. But I found that being "buddy-buddy" with them and not using "customer service-y" language really seemed to work for me and made them more receptive to any resolution to their problem I had to offer. They felt that I was on their side and listening to them.
Of course, in doing this, you do have to be careful to never bash the company you work for or their policies. I almost did this a few times. Not good.