сейчас столкнулся с подобной задачей. от себя добавлю:
1) поиск на различных языках
2) е и ё должны восприниматься одинаково
3) часто цифры воспринимаются пробелами, то есть по запросу "новая7папка" в результате выдает "новая папка"
4) использование спецсимволов в запросах
5) использование логических операторов в запросах
6) полезно узнать по какому алгоритму писался поиск, у нас например по следующему: http://pavelbelousov...сов-lucene-net/
юзабилити с разбором на конкретном примере, в идеале со статистикой "до" и "после", "с чего начинать тестировать web-портал"(как правильно разбить, какой подход применить и т.д.)