First, stock Android Email code does not support CRAM-MD5, that's a fact... but of course there is no way to tell with manufacturer specific, enhanced, versions.
Second, it takes two to tango -- and I wouldn't rule out the IT department first enabling CRAM-MD5 ("let's improve our network's security, oh, look, hash based authentication, that's cool") and disabling it or fixing it, after they discovered incompatibilities.
Just a theory, but...
Please understand that Aqua will always send the same authentication commands, same login, same password... it doesn't make stuff up on the spot (and there were no updates in the meantime). It's deterministic.
So something had to change outside of Aqua, that is, with the mail service. Knowing about CRAM-MD5, this was my guess. An educated guess, but still, only guess.
On the other hand, I don't believe in magic and evil fairies.
And I've seen many cases over the time of my working on Aqua where mail services (large and small) got changed and broken in various ways (and then sometimes fixed, sometimes not).
Just what comes to mind: Gmail, Yahoo, O2.pl, Apple's @me.com / @mac.com, Hotmail, QIP.ru, Yandex.ru, Telefonica.es, GoDaddy (my favorite)...