Совместно с Кириллом удалось определить в чем заключалась проблема. Может кому-то будет полезно. В нашем случае на ЦС, ЦР и АРМ администратора были установлены кросс-сертификаты, выданные Головным удостоверяющим центром. Попробовали удалить кроссы везде, после этого запросы стали подтверждаться очень быстро. Скорее всего это было связано с тем, что на ЦС, ЦР и АРМ админа отсутствует доступ в интернет, соответственно СОС, указанные в кросс-сертификатах, были недоступны, из-за чего проверка осуществлялась долго.