Well, exhaustive isn't always good, if you're not looking in the right place, it won't matter. The more exhaustive a search the better, but a good searcher will certainly be more efficient than an amateur.
Also, to note, it is certainly possible to combine classifications searching and keyword type searching. Basic keyword searches can be almost useless at times, and I don't think it is ideal at all nowadays to depend solely on classifications. A good, educated boolean search can turn up well qualified results and can help point you in the right direction fast. The USPTO's search interface allows some fairly complex boolean searches (though they can slow down the server, however, at least as of the last time I tried). Freepatentsonline.com, thats a site I haven't tried out but it seems to be user friendly and offers some search features that exceed the USPTO (and this site also allows you to search through patents using Google - just add 'site:freepatentsonline.com' to your search string). Delphion meanwhile, if you are a paid subscriber, allows for the creation of some insanely complex boolean searches and allows you to do more with the search results - (I would highly doubt that the average Delphion user gets as much out of the site as they could if they put their mind to it). Micropatent is probably similar, and supposedly allows you to search the text of patents issued before 1970. I do not have experience with Micropatent.
Tips for developing patent search skills....I would say...just become familiar with the classification listings on the USPTO's site (at the least, ideally it helps as well to become familiar with IPC and ECLA classifications too)
found here:
http://www.uspto.gov/go/classification/Become familiar with using the boolean search operators utilized by whatever site you are using to conduct searches.
Become more familiar with common patent terminology and structure, so you get a better idea of what you should generally be looking for.
You get better with experience.
Edited to add: since it hasn't been mentioned yet, once you locate relevant patents, 'reference' searching can be an easy and worthwile task to help ensure a more thorough search. Most patents reference similar prior art cited by the examiner (and some even summarize prior art within the patent's text). You can also search the USPTO and other engines pretty easily to locate forward references as well.