Exchange 2013 can produce IMAP issues when trying to authenticate. This is a known bug in CU9 and CU10 but in my CU12 scenario also happens.

The IMAPSettings EnableGSSAPIAndNTLMAuth atribute must be set to False in order to solve the problem.

Symptoms

Yesterday, when one of my users asked me how to configure the email client using IMAP I realized it was not working correctly. Outlook prompting for credentials multiple times and finally…

Error when testing IMAP configuration
Error when testing IMAP configuration

After enabling IMAP logging and restarting the services…

[PS] C:\>Set-ImapSettings -Server "EXCHANGE01" -ProtocolLogEnabled $True
WARNING: Changes to IMAP4 settings will only take effect after all Microsoft Exchange IMAP4 services are restarted on server EXCHANGE01.
[PS] C:\>Set-ImapSettings -Server "EXCHANGE02" -ProtocolLogEnabled $True
WARNING: Changes to IMAP4 settings will only take effect after all Microsoft Exchange IMAP4 services are restarted on server EXCHANGE02.

… this logs were generated

authenticate,NTLM,"R=""qv8b NO AUTHENTICATE failed."";Msg=""AuthFailed:LogonDenied,User: not found"";ErrMsg=AuthFailed:LogonDenied"

authenticate,NTLM,"R=""89fu NO AUTHENTICATE failed.\r\n* BYE Connection closed. 14"";Msg=""System.Security.SecurityException:The user name or password is incorrect.\r\n"

Diagnosis

After googling a bit this post showed me the solution (Thanks www.networksteve.com!):
http://www.networksteve.com/exchange/topic.php/Outlook_gets_Authentication_Error_on_IMAP4_on_Exchange_2013_CU9/?TopicId=52652&Posts=6

There is also this official KB3076376 related to this problem.

Exchange 2013 IMAP error KB3076376

As you can see, the problem only affects (supposedly) Exchange 2013 CU9 and CU10.
But my Exchange 2013 servers are currently CU12:

[PS] C:\> Get-ExchangeServer | Format-List Name, Edition, AdminDisplayVersion
Name                : EXCHANGE01
Edition             : Enterprise
AdminDisplayVersion : Version 15.0 (Build 1178.4)

Name                : EXCHANGE02
Edition             : Enterprise
AdminDisplayVersion : Version 15.0 (Build 1178.4) 

So, obviously, "installing Cumulative Update 11 or a later cumulative update for Exchange Server 2013" does not work for me.

Solution

Anyway, I could solve the problem by applying the workaround: Change the atribute EnableGSSAPIAndNTLMAuth value of the IMAP settings from True to False

[PS] C:\>Set-ImapSettings -Server EXCHANGE01 -EnableGSSAPIAndNTLMAuth $False
	WARNING: Changes to IMAP4 settings will only take effect after all Microsoft Exchange IMAP4 services are restarted on server PROBUZ21.

[PS] C:\>Set-ImapSettings -Server EXCHANGE02 -EnableGSSAPIAndNTLMAuth $False
	WARNING: Changes to IMAP4 settings will only take effect after all Microsoft Exchange IMAP4 services are restarted on server PROBUZ21.

…and restart IMAP4 services on the Exchange servers…

Restart Exchange IMAP service

…so that the problem is solved!

Success when testing IMAP configuration