Для меня идеальный вариант это разработка внешней COM компоненты (dll) которая устанавливается на сервере 1С, на вход получает: Сообщение, Имя ключа установленного в системе, Пароль для ключа. На выходе выдает подписанный XML файл.

Подключение к серверам ГИС ЖКХ планируется через туннель sstunel (http://www.cryptocom.ru/demo/cryptotunnel.html).

Вариант клиент сервер не подходит т.к. конфигурацией (программой) пользуются разные организации и разворачивать у себя web сервер они не будут.
Так же т.к. часть обменов будет выполнятся в фоновом режиме без участия пользователя весь механизм будет работать на стороне сервера 1С (1С работает по трехзвенной архитектуре: СУБД, Сервер 1С, Клиентские приложения на клиентских ПК).

Но в целом это должна быть библиотека которая ставится у заказчика на сервере 1С. У всех установлена Windows.
У клиентов уже обычно есть лицензии на Крипто-Про CSP версии 3.9, а вот с лицензированием ".NET Крипто Про" как Вы верно заметили есть проблемы.