Boxes and Arrows has a great little article on making advanced search more usable to people other than the “most fanatical users”:
Tim Bray wrote, “The people who do use Advanced Search are your most fanatical users, the professional librarians, spooks, and private investigators.â€
Even if you skim through most of the article, check out the final few paragraphs. I really like the model they are describing for a just-in-time, fully customizable, no-more-than-needed advanced search that pops up after the user realized their simple search didn’t really get them what they needed.