There is an interesting point in your question:
I thought about storing his password on his computer, and getting the web page to send it to me. I don't think that would make them feel safer though.
Do you want the users to be safe, or to feel safe ? That's not the same thing.
If you store the password on your server, you become responsible for it. There are some tricks which can be used to reduce the risks of leakage, but risks will still exist. For instance, if you store the emails in encrypted form in the database, then the server software will have to decrypt them before usage, so the server must know the decryption key, but that key needs not be known to the database; it could be stored in a file, and decryption done on the server (not with SQL-based cryptographic abilities offered by the database). This may provide some protection against SQL injection attacks. It is a delicate dance: if the server can access the stored passwords alone, then dumping the whole server contents (e.g. a complete hard disk image) must grant access as well; any encryption key must be there. Encryption, in that case, is a bet on the idea that attacks will be partial: an attacker will dump the database contents, not the whole disk.
A better system may look like this:
- For each user u, a random symmetric key Ku is generated.
- The email password for user u is encrypted with Ku; that's what is stored on the server.
- Ku is NOT stored on the server, but on the client.
- Upon connection, Ku is sent from the client to the server. The server uses it to recover the email password, in RAM only; the decrypted password, and Ku, are never written to files or database.
Storage of a client-specific secret value on the client, sent back to the server: that's a HTTP cookie. Be sure to mark it Secure and HttpOnly, and to use HTTPS for all the connections.
With that system:
- The emailing password is not stored on the client system, and thus won't be put at risk when the user's smartphone is stolen.
- The server's permanent storage (files, database) does not allow password recovery. An attacker who steals the whole system (he grabs the machines and makes a run for it) will not be able to obtain the passwords, regardless of how much computing power he dedicates to the tasks (assuming that the encryption was done properly, of course)(this contrasts with password hashing, where weak passwords can still be cracked, at a cost).
- If the user loses his cookies (e.g. he switches from his phone to his desktop computer, and has no syncing system between the two), then Ku is lost and the user must re-enter his email password.
The latter point is, again, inherent. If your server does not store enough data to recover the email password without the user's help, then... the server cannot recover the email password without the user's help. If the user is also helpless, then the data is lost.