Another clue perhaps:
I downloaded Thunderbird and gave it my gmail address. It proceeded to setup the account and (IMAP) and immediately downloaded two messages. But, when I used it to send (i.e. from gmail) it appeared to work but didn't deliver anything. So it's not just MAIL.