As far as I've found, there's no concept of ru_RU.UTF8 locale on Windows server. That means no module can format the date right way! My solution follows the well known practice: use iconv to convert from cp1251 to utf8.

Create a file /includes/winlocale.inc:

// This is wrap functions to fudge M$ Windows, which is missing ru_RU.UTF8 locale

define('UTF8', 'ru_RU.UTF8');
define('WIN', 'ru');

function tutlocale($category=false, $locale='ru')
{
	static $iconv=false;
	
	if(false===$category) {
		return $iconv; // whether sould we do iconv or not
	} else {
		$locale = setlocale($category, UTF8);
		if(false===$locale) {
			$locale=setlocale($category, WIN);
			if(false!==$locale) {
				$iconv=true;
			}
		}
		return $locale;
	}
}

function tutstrftime($format, $timestamp=false)
{
	$iconv=tutlocale();
	if(!$timestamp) {
		$res = strftime($format);
	} else {
		$res = strftime($format, $timestamp);
	}
	
	if( true===$iconv) {
		$res=iconv('CP1251', 'UTF-8', $res);
	}
	
	return $res;
}

Add a string

require_once './includes/winlocale.inc';

to the file /includes/common.inc inside the function _drupal_bootstrap_full() where all requires come.

use tutlocale(LC_ALL) instead of setlocale(LC_ALL, 'ru_RU.UTF8') and tutstrftime(...) instead of strftime(...).

Maybe someone has better solution?