У меня тоже такая же ситуация, при запуске Outloоk выскакивает сообщение, понимаю что причин может быть куча, но у меня это ситуация изначально идет после поднятия эксченджа 2010 с завязкой с 2008R2.
И причем ставишь галку запомнить, он не запоминаеть его. как с этой фигнюшкой разобраться. как обновить сертификаты?