Нашел заданный мною вопрос, решил раписать что выяснилось, пока решали проблему.

Как и говорил ранее, служба (работающая из-под системного аккаунта) использует хранилище сертификатов в HKEY_USERS\.DEFAULT. Установить их туда можно и без собственных программ, например воспользовавшись планировщиком, точнее его командой at:

at 09:21 /interactive "C:\WINNT\system32\rundll32.exe" shell32.dll,Control_RunDLL "C:\WINNT\system32\inetcpl.cpl",Internet Options

В заданное время появится диалог настроек Internet Explorer, откуда есть возможность установить сертификат.

Сервер, к которому должна коннектится служба, необходимо занести в список доверенных через консоль gpedit.msc (User Configuration -> Windows Setting -> Internet Explorer Maintenance -> Security).

Но самое интересное заключается в том, что служба не будет работать с компонентом XMLHTTPRequest если ей не дать возможность создавать этементы пользовательского интерфейса. Т.Е. в настройках службы необходимо включить флаг "Allow service to interact with desktop". Но этот флаг дает возможность службе создавать элементы пользовательского интерфейса только в случае, если в системе зарегистрирован какой-либо пользователь. Т.е. на сервере, где редко интерактивно регистрируются пользователи и этот флаг практически бесполезен.
Необходимость создавать UI-элементы связана, как я заметил, с тем, что в некоторых случаях копонент отображает диалоговые окна, например запрашивающие у пользователя подтверждения на доверие сертификату сервера, подтверждения выбора пользовательского сертификата, возможно еще какие-то.
Вот такое, на мой взгляд, "некорректное" поведение компонента было замечено. Действительно, выдавал бы он ошибку в тот момент, когда пытался создать UI элементы. Ведь если проделать все вышеприведенные действия — ничего более у пользователя запрашивать нет необходимости.
Об этой "фиче" можно было бы и сообщить в Microsoft. А впредь для таких задач использовать другие решения, например OpenSSL.