Are you connecting to Exchange 2003? If yes, Mail requires Exchange 2007 and higher. Your iPhone can connect but not Mail. You would have to setup as POP in Mail. Microsoft Entourage 2008 connects to Exchange 2003. It's old End of Life software so it will receive no further updates.
If you are using one of the newer versions of Exchange you might need to turn off AutoDiscover settings. This link has directions for Microsoft Outlook:
http://www.officeformachelp.com/outlook/exchange/autodiscover/
See this link for help with Mail:
**(Fair disclosure: OfficeforMacHelp is my site. I may receive some form of compensation, financial or otherwise, from my recommendation or link.)