How are apps like Mail+ connecting to Exchange, while Apple's Mail.app is blocked by my IT dept? My IT department has this great idea: if you want to read your work email on your personal device, you have to give us total access to the device. Well, no. It's my personal device, you can't have it. So I can't have work email.

Then I discover there are apps for Android that really don't care what my IT dept thinks, and they connect to Exchange for the emails anyway. Then I discover Mail+, which does the same thing in iOS: Connecting to my company's Exchange server without the profiles installed, and allowing me access to my work email.

My question is this: How are these apps connecting to the Exchange server? What is different about the way the iPhone connects with native email accounts? Is there a way to make the native accounts work without the profiles installed by my IT dept?
There are certainly a lot of variables here, some are.

The way traffic is 'managed' on the network that you are on.

There are many ways an IT department could prevent their network participants from accessing certain resources, I will explain a few.

DHCP &amp; DNS.
  Your specific device may be configured by reserved DHCP to use a different DNS server than everyone else. This may prevent external email services (possibly OpenDNS). You could try manually configuring your DNS to 8.8.8.8 (Googles service) and test again. 
 *This will still fail if for instance the IT department have also restricted DNS traffic on port 53 to their own DNS service exclusively.

Level 7 Firewall capability.
  A firewall can specifically see email traffic and through the creation of rules 'shape' traffic to fit an IT policy. This firewall could then 'see' Apple mail type conversation and block it, another email application may not behave the same way therefore failing to trigger the 'shape' match and ignoring it.

Mail servers can also be configured to use custom configurations, alternative port's could be used or your application may even use a proxy service or VPN (that could be hardcoded into the app)

That said and if your specific corporate IT policy permits, you could always 'investigate' using a VPN of your own if you wanted to 'experiment' (internet search 'personal vpn service') This would enclose your port 25 activity within a VPN tunnel.

Incidentally, I think it's worth mentioning.  When your IT department ask for you to accept an Android or iOS device management policy, they do not actually have access to your personal email accounts. They can enforce certain policies, for instance forcing a device to have a lock code, password complexity, length. Other capabilities depend on the device but neither currently have native support for location tracking.