So I have discovered a few things:
a) it helps to turn up the logs for IMAP
b) When your pre-windows 2000 login for an account does not match your exchange alias (all can be found in a domain user account profile) you need to use the following method to login:
domain\login\exchangealias
I did not need to use a FQDN, I could just use the short name of the domain. In our case our domain logins differ from exchange aliases. So far as I can tell, but I cannot test, if your pre-2000 login and exchange alias match, you should be able to login with
domain\login
This resolved my issue right away.