O que você poderia fazer nesse caso, é criar um serviço do Windows executando com privilégios LocalSystem e se comunicar com o provedor de credenciais.
Quando um usuário insere suas credenciais no ICredentialsProvider, ele entraria em contato com o serviço do Windows e o serviço manipulará a autenticação.
Após uma autenticação bem-sucedida, o serviço deve verificar se essa conta está presente localmente no sistema. Caso contrário, crie uma nova conta local com NetUserAdd e faça login com essa conta no sistema.
Tenha em mente que o ICredentialsProvider não tem os privilégios para criar uma conta local ou usar a maioria das funções Net *, por isso estou sugerindo a criação de um serviço do Windows com PrivS do sistema local.