Суть проблемы в том, что ваши сертификаты видны через менэджер сертификатов, а вот IE8 чихал на это и всегда показывает пустой список. Соответственно ничего не работает. Оказывается это известная проблема и для нее есть хотфикс, но он особо не офишируется и не доступен через центр обновления. Имя ему - KB977222.
P.S. Проблема актуальна и для Windows Server 2008.
P.P.S. Напоролся на это при настройке КриптоПро CSP.
