Ok, this turned into a major project.
Getting IMAP to work for downloading his mail was fairly simple. Once all the settings were correct in the phone it just worked.
Sending email turned into an adventure. The phone doesn't let you specify the port number to use, the software presumes to know the right port. The problem is that the phone has two options for secure SMTP - STARTTLS, which defaults to port 25, and SSL/TLS, which defaults to port 465. Exchange does STARTTLS and does not support SSL/TLS for SMTP. However, since the server has one IP address, and we need to allow unsecured connections to port 25 internally, we're accepting STARTTLS on port 587 (which is a valid port), and just because we can, I also set it to accept STARTTLS on 465.
See the problem?
If I configured the phone for STARTTLS it tried port 25, which died at the firewall. If I configured it for SSL/TLS I could see it hit the Exchange server - but it died there because Exchange wouldn't accept the connection.
I started thinking about setting up a second IP address on the Exchange server, then having the existing IP listen unsecured on port 25, as it is, while having it listen on the new IP on a secured port 25. Then mapping port 25 from the outside world to the new IP.
While looking at that, I had a better idea. The PIX firewall can do port translation. There is no reason the external port 25 has to map to an internal port 25. I could map external 25 to another internal port, say 588 (which is what I used), and tell the secure SMTP server to listen on that port as well. Simple. Well, except that I haven't really used Cisco IOS in years, and I'd never configured port mapping on a PIX myself. So it took me a while, but I did get the mapping working to solve the connectivity problem.
Now his phone could talk to Exchange and connect successfully with STARTTLS. It just wouldn't send any mail.
If I temporarily pointed port 25 to the unsecured SMTP server, it worked. Even if I temporarily reconfigured that server to be secured just like the other one, it worked. It just won't work on the second, secure server.
Obviously there is some difference between the two of them, but I can't find anything. I've been over both configurations with a fine toothed comb, and even if I configured them identically - one works and the other doesn't. Unfortunately, I can't setup the one that works to be secure, because that breaks a LOT of stuff inside the company.
And, to further increase the oddity - my account has always been able to send email on the secure server. Even if I configure my login on his phone, it works. So it is definitely related to the account and which virtual server (default or secure) it is connecting to.
Comparing the two accounts I've been able to determine that if I add his account to the 'Enterprise Admins' domain, then he can send email on both servers too. That’s what I've done as the short term fix so he can have it working on Monday as requested.
So there seem to be two long term fixes.
1. Find the difference between the default SMTP server, setup long ago, and the secure SMTP server I originally setup a few weeks go. (And deleted and recreated twice tonight in testing.) This seems like the better solution, the default server works with normal user accounts, even when set to require secure connections, so another server should work just like it if the differences can be found.
2. Find out what added permission the 'Enterprise Admins' group has that allows it to work on the secure virtual server, and then give that ability to the standard user group. Unfortunately that may turn out to be too permissive, so this may not be a real option. Another reason #1 would be better.
We don't need a phone to test this, any SMTP client from outside the firewall (like Mozilla Thunderbird) would suffice. We may just need a PC and to setup some connection from outside. It should be the same for any non-admin user, and we have a test user in the system.
I think it may be that past admins did something to lock the server down, which changed some permissions - and the new virtual server doesn't have them. I've compared directory permissions, owners, etc, but I don't see a difference there.
And with that, I need dinner and sleep.
This seems like the kind of problem you need to see the box to fix, but I figured it wouldn't hurt to toss it out there. It wouldn't be the first time someone has said "Oh yeah, I saw that last year, this is what we had to do." I'll buy you a beer or something... (This is why I stressed Active Directory and Exchange for the senior position I'm hiring for - I came from the UNIX/Linux world and this MS stuff is bizarro world to me.)