When I do my introductory talk about search marketing at our Search Engine Strategies shows, I explain that search marketing it is the combination of SEO and search advertising.
SEO is like getting PR -- with a little appropriate effort, you might get some nice free publicity, but no guarantees. Search advertising is guaranteed -- and that's why you pay so much for it!
In Compare and Contrast: SEM and SEO from ClickZ, Kevin Lee does some comparing of his own. SEO for many sites is mostly about clearing the hurdles that can make a site non-search engine friendly. Fix the problems, and the free listings tap might start flowing with relatively little need to watch over it on a daily basis.
Search advertising -- what he calls paid SEM -- isn't a fire-and-forget activity. It needs lots of watching and may involve skills completely different than SEO.
SEO and search ads do have some things in common, as he outlines -- but he predicts that the two may diverge even further down the line.
I agree -- and it's also why you might find yourself employing two completely different companies. Concerned about your free listings, especially in terms of how they might have an impact on your company's reputation? Turning to a company skilled with paid search but not organic might not be helpful. Think of it back in the "real" world again Plenty of companies have both PR firms and advertising firms.
Meanwhile, Gord Hotchkiss points out at MediaPost in The 70/30 Rule of Search how despite the fact that searchers pay the most attention to free listings on search engines, marketers spend the most money on getting positioning through search ads. That mix, he argues, should change to better reflect positioning in the real "prime" part of a search results page.