Na execução do Windows Vista e da introdução do UAC, a Microsoft alterou a maneira como os direitos de administrador são fornecidos aos usuários e aplicativos, e muitos aplicativos tiveram que alterar sua arquitetura para acomodar as novas regras.
A Microsoft forneceu este documento, com várias estratégias diferentes para lidar com essas alterações: link
Muitas das opções envolviam dividir o binário em vários executáveis, para que eles pudessem ser executados separadamente com diferentes níveis de privilégios e configurações de usuário.
No seu caso, a opção intitulada "O modelo de serviço de back-end" no documento acima é a mais adequada para a solução que você descreveu. Ele envolve a separação da funcionalidade que requer privilégios administrativos e a colocação em um serviço do Windows, que pode ser configurado para ser executado como um usuário privilegiado sem exigir a chamada interativa do usuário.