При формировании скриптов указывал, что кодировка страниц будет windows-1251. В результате получил такой код (на стр. результатов поиска):

<div id="ya-site-results" onclick="return {'tld': 'ru', 'language': 'ru', 'encoding': 'windows-1251', 'htmlcss': '1.x', 'updatehash': true}"></div><script type="text/javascript">(function(w,d,c){var s=d.createElement('script'),h=d.getElementsByTagName('script')[0];s.type='text/javascript';s.async=true;s.charset='utf-8';s.src='http://site.yandex.net/v2.0/js/all.js';h.parentNode.insertBefore(s,h);(w[c]||(w[c]=[])).push(function(){Ya.Site.Results.init()})})(window,document,'yandex_site_callbacks');</script>

Испытал (тестовая страница http://www.teplo3000.spb.ru/test3.asp) - поиск выдает кракозябры ((, видно что результат в кодировке UTF-8..... что делать?

(пробовал даже исправлять s.charset='utf-8' на s.charset='windows-1251')