Eu encontrei a causa, e não é outro senão o nosso querido amigo UAC.
Eu tropecei nisso por experimentação, depois de relembrar que (dependendo das configurações) o UAC solicitará aos membros do grupo Administradores a elevação de privilégio, enquanto o Administrador interno obtém elevação automática sem avisar. Isso me levou a pensar se era um problema ao solicitar um usuário remoto.
Descobri que, com o UAC desativado, tudo começou a funcionar como esperado.
Infelizmente, parece não haver nenhuma configuração que permita que esses itens funcionem com o UAC ativado. Eu tentei todas as configurações de política relacionadas ao UAC (como "elevar administradores sem avisar") no caso de elas resolverem meu problema como um efeito colateral, mas não encontrei alegria lá.
Acabei de inicializar um servidor 2008R2 para checar novamente o que eu disse na pergunta sobre versões anteriores, e é de fato que com o UAC ativado, ele permite o acesso em questão do mesmo UserA no WorkstationA.
Portanto, parece que esse comportamento mudou em 2012 ou como resultado de uma atualização.
Então eu tenho uma resposta, mas ainda não tenho solução. Não pretendo marcar esta resposta como aceita.