If it's any inspiration I recently started hitting an 'out of the blue' issue with mail access (in this case, google Apps) whereby connections were rejected, asking for password etc, when it made no sense. This on a system that had been stable and reliable for months.
I can't remember the exact details, but vaguely... the root problem turned out to be a newly acquired and configured Android phone. Its mail client was opening multiple IMAP connections, and blowing some connection limit that was set at the server, such that other mail clients like my
PC, iPad etc, were sometimes refused connection. The fix was buried in the Android mail app's settings, limiting the number of IMAP connections, whereupon everything else started working reliably.
Sorry I can't be more specific, must learn to write things down so I don't forget so easily !