Forgive my ignorance, but are there any companies that provide proof that they encrypt users' passwords?
No. This is impossible. The whole model is broken. A less broken model is the use of asymetric keys for authentication that doesn't require the service provider to "promise" they'll keep your password secret.
This model, of course, is broken in its own way, in that if a user loses their private key, all their data is lost; there's possible recourse or password reset. It's also broken in that, if the company believes that a user's private key was compromised by a third party, they can't completely destroy that key until the user manually logs in and changes it.
Well, one could always leave one's private key with a trusted third party. So the public key model can accomodate those who are uncomfortable with the responsibility of keeping their private key secure. The password model however does not allow for allodial title to a secret.