It is entirely possible to keep secure data on a server that only someone else with the password can access. They don't store your password in plaintext, they don't test whether what you typed is the same thing they keep on their servers. If the password works to decrypt your data then your client can read the emails. If not, your client gets gibberish and knows your password was wrong. With a secure system your password should never be sent to the server at all.

Now, that doesn't mean it's trustworthy. There could be holes in the security, and I certainly would feel better controlling my own server, but it's not automatically insecure just because it's hosted by them.