Same boat here, Exchange on site behind our ADSL service.
The next MX record after our static IP is a backup mail provider so mail goes there when our ADSL is down, our set up is as follows;
1. We have pop access to the backup provider, 3rd party software on the Exchange server connects out and checks for new mail every 10 mins so when service is restored after an outage the missing mailing will start filing into your inbox within 10 mins.
2. This also means if we can get a temporary connection up (even if its a NAT'd 3G jobbie, mail will flow just slowly on the inbound as that 10 minute interval comes round).
3. Our backup mail providers also provides webmail access so remote workers who can't get into our OWA can use that.
Take from that what you will. A VPN isn't a bad idea, just set up an OpenVPN server your end and install the client on their Exchange box then they can always connect to you even over 3G.
(An easy way to start but maybe not the most secure is to download the OpenVPN Access Server virtual machine from their website, its almost ready to go out the box. We have a site-to-site link between two offices. If one end loses ADSL service [and thusly their static IP] we have an OpenVPN AS virtual machine at both ends and the client installed at both ends so it can be fired up and one server can dial into the other). My two pence, HTH.
--James. (This email was sent from a mobile device, this is not secure)