Picture this: You walk up to a local business, walk through the door, up to the first person you see and say "Hi, I'd like you to put this sticker on your window because I sell products that people who come to your establishment might like too." Said sticker is an address to your business.
Think it will be successful? Probably not.
Now let's try this scenario: Instead of asking for them to put a sticker on their window, you pick up one of their mailers to customers and ask them to put your address in the middle of one of their articles, again because readers of the mailer might be interested in your products.
Again, will this probably won't be successful. Your only chance in either scenario is going to be if said local business accepts advertising, in which case you're going to have to pay them to get your business advertised on their window or in their mailer.
Now let's think about quality. Sure the Joe Schmo business next door might take you up on your offer. But what if you tried to walk up to the biggest retail chain in your area and asked them to do the same thing? Would your request be granted? Doubtful.
This is, essentially, what clients want link builders to do for them. They don't want to offer anything of value content-wise, but they want people who have probably never heard of them before to just magically place their name and website address on their website. And it's just about as absurd as the above described scenarios.
So the next time clients are complaining about the fact that the links they get are only paid or only high quality, it's time to turn the tables on them.
It's not you, the link builder, who is to blame because I'm sure you've been successful with clients who have good content on their site, or at least a good reputation.
It's the client that needs work. You need to stop link building and start content development. And not just one piece of content that might not appeal to everyone, but several pieces. Think about developing the kind of content that Wikipedia would find as a suitable resource for one of their pages.
How-to guides, tutorials, detailed histories, facts about the industry, current trends, videos, and so forth. These are the types of content that people will want to link to. No one wants to just link to sales pages and product pages unless the page your targeting specifically says "here are some great resources to buy __."
What if your client refuses to add any link-worthy content to their site? Then tell them that, realistically, the only opportunities you'll be able to get for them are directories, paid advertising links, or other lower hanging fruit.
Why? Because authority sites link to valuable resources - not just products or sales pages, especially if it's you competing against thousands of other stores that offer the same items or services.
In short, your client needs to ensure that their site offers value. If it does, then it will gain links. If not, then they will have to settle for whatever they can get, and that may not be what they optimally are looking for.