I've been traveling recently. Travel gives you a great perspective on customer service. You're continually dealing with airlines, restaurants, hotels, etc. One of the things I've noticed lately is that you can divide people/companies into two types. One type wants to go by the book. If you ask them for something that doesn't fit into their predefined "boxes" their response is "sorry, can't help you". They might be really friendly about it, but they don't help you. The other type will look for a way to help you, even though you're asking for something unusual or something that isn't really their business.
For example, we go into several agencies and say we want to go out snorkeling to a different island than the usual one. Most of them give us the official response of "we don't go there" or "we don't have enough people who want to go there" and that's the end of it. But then we go to another agency and they say "sure, we can work something out, it may depend on the weather and what else we have booked, but we'll figure it out". That's the kind of service that brings me back for repeat business.
I just hope that my business is more like the second type. Obviously, you can't answer every single request but you can try to come up with something to offer. My staff will come to me and say "so and so wants xyz, what should I tell them". If possible, I'll say "give it to them". Lots of times it's not possible, and you can tell that the staff person just wants to say no. But often we can offer a partial solution or an alternative or a suggestion. It may or may not totally satisfy the customer, but at least you've tried.
Here's an interesting video from a customer service conference: (note: it's an hour long)