Gracias por contestar, courtois.
En efecto es como dices, mi pregunta en realidad era si habia alguna implementación alternativa.
Sin embargo, pudimos detectar que el problema no estaba en el acceso al registry sino en los permisos del Data Execution Prevention (DEP) del Windows.
Es decir, el proceso de registro funcionaba bien pero el S.O. bloqueaba el acceso al Web Service produciendo un error interno en mi aplicación cliente.
Dejo este link por si a alguien le ocurre algo similar:
http://support.microsoft.com/kb/875352
Gracias de nuevo.