There's not much info on the interwebs on why ssh authentication via pam_mysql fails, and there are definitely some misleading answers like
when logging in via ssh, the ssh daemon checks some files in ~/, so it can be done if the user already have a valid home directory.from this thread.
The real reason why it doesn't successfully authenticate is because ssh does a getpwent() call to check if the user exists on the system. If you're using just a PAM solution (which doesn't provide accounts), that call fails if there isn't any such local user. sshd then sets the password to '^H ^M INCORRECT' before passing it to PAM, which obviously thinks it's the wrong password. The simple (and probably unscalable - but then you should be using something like nss_mysql) solution is to add local accounts to the machines for these users. That will make the getpwent() call succeed, and sshd will authenticate successfully via PAM.
I've mentioned this earlier.