You will need to store the user's email password in a recoverable form. You can still encrypt the passwords, but you cannot hash them.
Storing your users' passwords in recoverable form does entail some security risks. If the database of user passwords is ever leaked, you've got a serious security breach. However, that's just the nature of your service. People normally recommend hashing to try to mitigate this risk, but since you can't use password hashing in your particular application, you'll have to use other measures to mitigate the risk.
Here is my recommendation for how to do it in as secure a way as possible. Set up a separate machine (or VM) that is used solely for the purposes of managing email passwords. It runs a service -- let's call it the password-keeper service -- that exposes a few simple APIs:
Register IMAP account. The caller provides information about an email account: e.g., the username and password. Your password-keeper service stores this information.
Read email. The caller identifies an IMAP account that was previously registered with your service. Your password-keeper service looks up the username and password for that IMAP account, connects to the IMAP server and authenticates to it, downloads any new email, and returns the desired email messages to the caller.
This password-keeper service is like a Hotel California for email passwords: passwords go in, but they never leave. The password-keeper service is responsible for storing passwords as securely as possible, and never exposing them to others. It might store the passwords in a separate database, encrypted under a special key. The encryption key might be stored in a configuration file that is accessible to this service, but not to anyone else. The password-keeper service can now control access to your users' email accounts. For example, it can perform secure logging (so you can track down intrusions), rate-limiting (to reduce the impact of a breach of your other systems), or other protections. You can also lock down who or what can access it.
Now, write the rest of your system to be a client of the password-keeper service. Configure the password-keeper service so it is only accessible to your code (and not to the public), and use strong authentication for your code's connection to it. Make sure that you never store users' email passwords anywhere else in your system. When the user supplies an email password to your application, you should immediately invoke the password-keeper service's "Register IMAP account" API, pass it the password, and delete all other copies of the password.
This will not provide perfect protection, but it gives you a place to stand: a way to get as much protection as possible, for your users' passwords. With this kind of approach and some diligence, I think you can provide a reasonable level of security to your users.
