途中経過ですが、とりあえず文字化けと日本語検索が出来そうです。
http://bit.cms-labo.org/ajax.html
上記サイトはEUC-JP環境のテストサイトです。
キーワードにホームと入力してみて下さい。
これで問題無いようなら、良いのですが・・・。
修正箇所ですが、前にeastbindさんが書いた
$moreResultsText = mb_convert_encoding($_GET['moreResultsText'],"EUC-JP","UTF-8");
$resultsIntroFailure = mb_convert_encoding($_GET['resultsIntroFailure'],"EUC-JP","UTF-8");
$searchString = mb_convert_encoding($_GET['search'],"EUC-JP","UTF-8");
の3箇所の修正で、日本語検索でキーワードがヒットするようになると思います。
そして文字化けですが、
ajaxSearch.phpで$result.=’<div class="FSF_ajax_result">’;などが書いてある下の箇所、
つまり、検索結果が出力される変数がHTMLタグと一緒に書いてあります。
その変数、例えば. $row[’pagetitle’] .なんかを
. mb_convert_encoding($row['pagetitle'],"UTF-8","EUC-JP") .
などに変更してあげれば、出力時の文字化けは回避されます。
ほんとはajaxSearch.phpをまるごとアップすれば良いのですけど、かなり弄くりまくって・・・・

あ、ajaxSearch.jsでencodeURIComponent()するのを忘れないようにして下さい。