oryth,
кодировать данные надо перед отправкой https://learn.javascript.ru/xhr-forms

oryth,
Почитайте http://xmlhttprequest.ru/, раздел GET и POST-запросы. Кодировка.

определили что кодировка параметра s почему-то в cp1166

destus,
Огромное спасибо!!! Ваша ссылка помогла.
Но мне все равное интересно, почему без encodeURIComponent в других браузерах отлично работает. и еще больше удивляет, то что на моей этой же страницы есть такой же абсолютно код (только поиск осуществляет не по фамилии, а по другому полю) без encodeURIComponent, и он работает в IE

Возможно остальные браузеры сами добавляют нужный http заголовок, а ie нет. И всегда нужно отправлять данные в utf-8.