SSH Prompts for password even though private keys are available, presented to server and known to it

Solution 1:

How is the user's home directory mounted? It sounds like, for whatever reason, the user's home directory is not available if the user is not logged in, so that sshd can't find the authorized_keys file.

Also, take a look at /var/log/auth.log on the server for any messages.

Update: if it's necessary to do password-less login, you can change the sshd_config file to look for authorzied_keys in a non-encrypted directory. http://www.openbsd.org/cgi-bin/man.cgi?query=sshd_config&sektion=5

I suppose something like this would work (not tested):

AuthorizedKeysFile /etc/ssh/pubkeys/%u/authorized_keys .ssh/authorized_keys

That should tell sshd to check for public keys in both the unencrypted location and the encrypted one. Check the man page for more info.