Only my 2p, not an expert, so use the proverbial pinch of salt :D
1) Blackberry WILL work. What they meant was that they did not have a push email blackberry compatible at your workplace. But it will work to access your mil perfectly
2) If the only business use you have for your phone is email, iphone works well. typing is all right, but I did not like the touchscreen keyboard.
3) the best business phone for me was (and is) the Nokia E90. Very stable, excellent keyboard, brilliant screen. E75 is good
4) you may also look at other platforms...