Mail does work for Exchange 2003 and 2007, what you might not be able to use is the setup assistant to make things easy.
My office has Exchange 2003 and I have everything working just fine with an IMAP connection. This may be disabled by your Exchange admins... you'll have to check. From that point find out the type of encryption (Password, MD5, NTLM), if you have SSL enabled (hopefully yes), and the domain name needed (your MS Domain, usually in all caps).
To get help from your Admins, rephrase your question of "how to setup Apple mail" to "how to setup an IMAP mailbox". Might lead to better answers and a working system.