Even if you're doing some kind of public-key cryptography, you're still going to have to store the private key at some location on the device, to decrypt the password for IMAP/SMTP/whatever authentication.
Is there some foolproof way to do this that I'm not aware of? How are you supposed to store a password for future retrieval, not in plain text or basically plain text (encrypted but with the key on the device)?