Ну вот в IE это довольно просто: в строке поиска если ткнуть мышью, то вываливается список ранее использовавшихся запросов, так вот по ним можно перемещаться курсором, а удалять банально клавишей Del
Есть еще вариант, который упомянут здесь:
http://www.kellys-korner-xp.com/xp_g.htm в вопросе Google - Remove Search History, но проверив я когда-то его пробовал проверить - на нескольких компьютерах разделов глубже HKEY_CURRENT_USER\Software\Microsoft\Protected Storage System Provider\SID_пользователя просто нет, возможно здесь имелись ввиду поисковые запросы Google Desktop Search
