Syntax error in response. Unexpected token: [atom: A00000003]

[test-in-prod]

Hello,

Trying to connect and authenticate with an Exchange 2010 SP3 server but getting this bizarre exception:

MailKit.Net.Imap.ImapProtocolException: Syntax error in response. Unexpected token: [atom: A00000003]
   at MailKit.Net.Imap.ImapCommand.Step()
   at MailKit.Net.Imap.ImapEngine.Iterate()
   at MailKit.Net.Imap.ImapEngine.Wait(ImapCommand ic)
   at MailKit.Net.Imap.ImapClient.Authenticate(Encoding encoding, ICredentials credentials, CancellationToken cancellationToken)
   at MailKit.MailService.Authenticate(String userName, String password, CancellationToken cancellationToken)
...

FYI, removed NTLM as authentication mechanism to no effect. SSL is also disabled.

IMAP Log:

Connected to imap://example.org:143/?starttls=when-available
S: * OK The Microsoft Exchange IMAP4 service is ready. SERVERNAMEHERE
C: A00000000 CAPABILITY
S: * CAPABILITY IMAP4 IMAP4rev1 AUTH=NTLM AUTH=GSSAPI AUTH=PLAIN STARTTLS IDLE NAMESPACE LITERAL+
S: A00000000 OK CAPABILITY completed.
C: A00000001 STARTTLS
S: A00000001 OK Begin TLS negotiation now.
C: A00000002 CAPABILITY
S: * CAPABILITY IMAP4 IMAP4rev1 AUTH=NTLM AUTH=GSSAPI AUTH=PLAIN IDLE NAMESPACE LITERAL+
S: A00000002 OK CAPABILITY completed.
C: A00000003 AUTHENTICATE PLAIN
S: +
C: <some base64 string here>
S: A00000003 NO Server Unavailable. 15
C: A00000004 LOGIN <username@domain> <userpassword>
S: A00000003 NO AUTHENTICATE failed.

Thanks!

[jstedfast]

This is the problem:

C: A00000004 LOGIN <username@domain> <userpassword>
S: A00000003 NO AUTHENTICATE failed.

The server should have responded with an A00000004 tag, not A00000003 (like it did).