Понимаю, что "Вопрос задан более 3х лет назад", но может кому интересно будет ))
Перед запуском vim в консоли делаю
chcp 1251
и потом, если возникают проблемы, обратно
chcp 866
В .vimrc такие настройки:

if has( "gui_running" )
...
else
    if has( 'win32' )
        set encoding=cp1251
        set termencoding=cp866
        set keymap=russian-jcukenwin
    endif
endif

Переключение языков производится сочетанием Ctrl-6. Подробнее см. справку в Vim

:help keymap
:help enc
:help tenc

UPD:
Поюзал консольный Vim под виндой, и обнаружил ещё кое-что

• Если в свойствах консоли выбрать какой-нибудь TrueType шрифт, то нужно делатьset termencoding=cp1251
  
• Чтобы не запариваться с переключением chcp 1251 ... chcp 866, можно сделать алиас для cmd.exe: DOSKEY vim=chcp 1251 $T vim $* $T chcp 866, поместить этот алиас в скрипт и настроить автоматическое выполнение скрипта при старте cmd.exe (будет что-то вроде .bashrc для bash). Про алиас и скрипт подробнее здесь: stackoverflow.com/a/21040825/3047301.
  
  

ОС Win 7 x64, Vim 7.4.