I have had UAC turned off for quite a while now
Suspeitei que o UAC estava desligado durante a leitura da pergunta.
Muitas pessoas entendem mal o que a opção "Executar como administrador" faz. Isso não tem nada a ver com o uso de uma conta chamada Administrador ou uma conta que faça parte de um grupo chamado Administradores. Tem tudo a ver com a execução de um programa de forma que o UAC reconheça que o programa tem privilégios elevados. A opção "Executar como administrador" não afeta a conta do usuário que está sendo usada para executar o programa.
(Eu queria que a opção fosse chamada de "Run Elevated". Como está, o fraseado dessa opção confundiu muita gente.)
Chame-lhe uma opção de nome confuso, se preferir, mas se você Shift + "clicar com o botão direito" em um ícone, você poderá ver a opção "Executar como Administrador" somente se o UAC estiver ativado . Caso contrário, esse item simplesmente não existirá. Isso pode ter mudado um pouco com os sistemas operacionais mais recentes, mas é assim que isso funcionava no Windows 7 (e no Windows Vista).
Portanto, não estou surpreso que esse atalho de teclado não funcione. Eu não usei este atalho regularmente, mas parece que esse atalho simplesmente executa a funcionalidade de um recurso que nem sequer existe a menos que o UAC esteja ativado.