Мл, вот я балбес - отправляю заголовки перед открытием соединения...
Решение проблемы:
req.open("POST", "index.php", true); // открываем
req.setRequestHeader("Content-Type", "application/x-www-form-urlencoded"); // пошли заголовки
req.setRequestHeader("Content-Length", searchStr.length);
req.send(searchStr); // отправляем данные