@PaoloM: Thanks for the heads up PaoloM - unfortunately I can't reproduce your fix. The mail app won't connect to the exchange server at all, thus it doesn't allow me to save the non working account. So, when I close and restart the Mail app, there's nothing there and I have to go through the same loop each time.
To be honest, I'm starting to think that there's something going on with the way our Exchange server is set up as I have vague recollections of our iOS users not being able to access and they had to specify some custom permissions/access. I'm going to speak to my Exchange guy on my team tomorrow and see if he knows what it may be.
Thanks for the suggestion though!