And herein lies the problem (I didn't notice it before). Running the same command produces the same errors, but different results:
*.imap.yahoo.com vs just imap.yahoo.com in my earlier post. For those that don't really know what that means, it's a wild card, allowing all domains that end in "imap.yahoo.com", including "palm.imap.yahoo.com", as opposed to only allowing "imap.yahoo.com".
openssl s_client -showcerts -connect palm.imap.mail.yahoo.com:993|openssl x509 -text
depth=0 /C=US/ST=California/L=Santa Clara/O=Yahoo! Inc./OU=Yahoo/CN=*.imap.mail.yahoo.com
verify error:num=20:unable to get local issuer certificate
Oddly enough, the currently active certificate expires EARLIER than the certificate that was active when the problem occurred (by 1 day), and yet they have nearly the same generation date (both in 2009!).
Not Before: May 8 00:45:06 2009 GMT
Not After : Jun 8 22:36:53 2011 GMT