I get more and more requests from clients who are adament about not using directories, or article directories to build links.

What other type of options are there to get relevant one way links besides manually contact each appropriate webmaster and trying to work something out?

Buy them! There are lots of opportunities to buy links, whether those be one time fees or recurring. Think of it as buying ads on other people's sites. It is perfectly legit, can increase link popularity and may even send traffic in and of itself.

IMO, buying links is a much better use of resources then sending unsolicitated requests asking others to link to your site. ;)

Creating an amazing tool!!

Wow okay,
Whats the going rate?

Aah yes - link bait! That is really the best way to obtain links. Create a valuable resource whether that be a tool, a white paper, a case study, a top 10 list, something humorous, etc. that will naturally attract links. Sometimes this is easier said then done.

As far as our industry (search marketing) goes, Rand Fishkin (http://www.seomoz.org/) is one of the most brilliant at creating link bait.

There can only be one!!! :D

For some industries, good linkbait includes worksheets, checklists, forms, etc. I look for things in that market that would be extremely useful to the target audience.