Like many others, I too have noticed intermittent mail-check authentication failures since around mid-November. I use Eudora 6.2.4 with 3 Verizon accounts and another at my employer; only the Verizon ones have this problem. I see the same thing with Mail.app (version 3.5).
In my case, the problem seems to be 100% correlated with 2 of Verizon's pool of about 15 servers. Please see my postings at
http://forums.verizon.com/vrzn/board/message?board.id=FiOS_Internet&thread.id=10 18 .
I have no explanation as to why some user's Mail Preferences are reverting to APOP. I can see that Ernie Stamper's suggested workaround of setting the preference to "Password" works on Verizon, but IMHO is a bit risky, since that results in your name and password being sent in the clear. I have found that for Verizon users at least, setting the preference to "MD5" is better; that's secure, and it'll work most of the time, but if it fails, Mail will immediately fall back to "Password" which will always work -- that's still unsecure but at least it does that only occasionally rather than every time.