ive been thinking about this for a bit due to the fact that you should never store user passwords in plaintext. so I have came up with a possible solution for you.
When a user signs up for a new 'service' to their account (e.g. they add gmail or yahoo, etc. ) what you are going to have to do is:
Ask the user for their site password again (and validate it)
Hash their password again with a new random salt (which you should store) (with a different hash algorythm to what you use for your main password store) DO NOT STORE THIS!! from now on I will refer to this as KEY_A
generate a passworded dsa or rsa key with KEY_A as the password for the keyfile. This will be used as the enctyption key for the next step
Use a Secure encryption method (maybe mcrypt if in php since it is built in) and store their 'encrypted' password
When a user logs in, and a new session is created rehash their password with the same method used in step #2, Encrypt it with a key that is derived from something that is unique to their session but not stored ( Lets say user_agent + session_start_time + their Ip address + a user specific salt ). Store this encrypted value in a http_only cookie, clear said cookie on logout, force them to login again if the cookie is not present.
Now you have a method of storing their gmail/hotmail/etc. credentials in a manner where you have no direct way of knowing how to decrypt them without the password that they use for your service.
It would most likely also be prudent to make sure that you do not store some of the components used in encrypting the cookie ( so at the least disable user agent logging in your webserver config. )
Now in order for you to perform a iMap login (or something similar. you would simply have to decrypt the http_only cookie from step 5 to get KEY_A, use KEY_A to unlock the RSA/DSA key, then use the unlocked key to decrypt the password to their service, then perform the iMap transaction, and just to be paranoid re-zero (in php you can just call unset() )the variables which contain their plaintext password, KEY_A, and their unlocked rsa/dsa key the line of code after they are no longer needed.
In addition to this make sure that your DNS service is also setup securely. (force DNS-SEC, maybe even setup your webservers dns resolution to go via a service network interface and not the web-visible one and perform DNS resolution via a different 'non-related' web visible IP address.) Make sure that your https certificates are completely up to scratch.
Because you will be effectively sending peoples private passwords over the web the last thing that you want is someone flooding your web server's ip address with udp DNS resolution packets redirecting lets say 'mail.google.com' to a custom imap proxy that they have created for the purposes of sniffing passwords.
The only downside to this method (that I can think of) is when the user changes the password to your service they will need to re-enter the password to all the other email providers that they have registered with it. (because the stored encrypted password will be no longer valid. )
And last but not least ( im assuming that this is will be done, but I have no way of being sure. ) delete ALL debug code related to these routines prior to going live!
The whole key to this is ensuring that KEY_A cannot be derived from anything that you store (so dont shortcut by simply re-hashing the hash of their password, hash in a different manner, with a different salt.)