OK, encontrei a resposta para minha própria pergunta. Acontece que esse aplicativo ridículo de solicitação de senha que não respeita o sudo é chamado de PolicyKit. De jeito nenhum a maioria das pessoas sabe sobre este aplicativo, por isso é difícil para o Google. Esta questão colocará um fim nisso!
A correção é simples: em /var/lib/polkit-1/localauthority/50.local.d, crie um arquivo chamado disable.pkla (ou o que você quiser, contanto que ele termine com .pkla) com o seguinte conteúdo:
[This name does not matter]
Identity=unix-group:admin
Action=*
ResultActive=yes
Faça logout e volte, e divirta-se!