Como o diretório pessoal do usuário é montado? Parece que, por alguma razão, o diretório pessoal do usuário não está disponível se o usuário não estiver logado, para que o sshd não encontre o arquivo authorized_keys.
Além disso, dê uma olhada no /var/log/auth.log no servidor para qualquer mensagem.
Atualização: se for necessário fazer login sem senha, você pode alterar o arquivo sshd_config para procurar por authorzied_keys em um diretório não criptografado. link
Suponho que algo assim funcionaria (não testado):
AuthorizedKeysFile /etc/ssh/pubkeys/%u/authorized_keys .ssh/authorized_keys
Isso deve dizer ao sshd para verificar se há chaves públicas no local não criptografado e no criptografado. Verifique a página do manual para mais informações.