How are apps like Mail+ connecting to Exchange, while Apple's Mail.app is blocked 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.