De alguma forma, começou a funcionar novamente. Para ajudar outras pessoas na mesma posição, adicionarei o passo que tomei para resolvê-lo:
Há alguns meses instalei o Spybot Search & Destrua e use a ferramenta de imunização fornecida. Nas minhas pesquisas sobre esse tópico, observei algumas pessoas mencionando que o cliente Cisco precisava adaptar um arquivo host para funcionar. Aparentemente, o Spybot decidiu que o cliente não tinha permissão para fazer isso. Depois de desfazer a imunização e desinstalar o Spybot, o serviço vpnagent começou a funcionar magicamente!
Não tenho 100% de certeza de que essa foi a solução real, pois minha VPN funcionou antes mesmo quando a imunização ainda estava ativa. No entanto, suspeito que o conflito entre o Spybot e o antivírus Avira possa ter algo a ver com esse comportamento não determinístico.