Graças à sugestão do @ DevilaN, resolvi o problema.
A tentativa de ssh-copy-id retornou um erro "permissão negada em authorized_keys". Como era um erro de permissão, voltei para verificar a propriedade e as permissões no arquivo authorized_keys e, apesar de ter configurado a propriedade para o usuário neste arquivo (como na pergunta original), claramente eu ou meus colegas faziam algo desde a configuração inicial que levou a que a propriedade fosse alterada para "raiz".
Foi um problema de propriedade simples.
chown theuser:theuser authorized_keys
e voila, ssh está funcionando.
Para qualquer pessoa que encontre essa resposta por meio de uma pesquisa do Google: parece que a propriedade do usuário errado do arquivo authorized_keys fará com que uma tentativa de login do ssh falhe silenciosamente sem retornar ou registrar em log em qualquer lugar que seja um erro de permissão -copy-id.