Jacek Gwizdka of Rutgers University presented on a series of studies he completed on task difficulty and search. The dependent variable on the level of difficulty were relevance, so the more documents found the higher the task difficulty. The strongest predictor was the number of pages visited, so the more documents people opened, the harder they found search to be. This seems to follow my intuition, that if we can return the best documents, higher in the results and give the user a clear good document, they will find search easier, and better.
He found that there was a correlation between objective and subjective task difficulty. He found that subjectively difficult tasks were related to more search actions, greater than objective difficulty. So if people think the task will be hard, they do more work, regardless of the objective assessment of difficulty. He also found that better search task outcomes are associated with lower levels of objective difficulty. In terms of the efficiency of the systems, people are slower on more complex systems. They find more complex systems to have a higher level of subjective difficulty.