Currybet has a series of posts reviewing the search features of newspapers’ websites. This post summarises the results. He rates The Times, The Guardian and The Daily Mail most highly. I would agree with the latter two, although the last time I tried to search TimesOnline it was a complete nightmare.