Ok, you have to make a decision as to what is important and what is not.
If getting a high availability connection to the internet is not possible, or not important enough to the necessary money on, then your options are very limited. Think about it for a moment.
You have several scenarios you have to account for
1/ no internet connectivity for your mail system
2/ efa server down
3/ exchange server down
your goals seem to be
(a) provide the ability to send mail at all times for all the users
(b) provide the ability to receive mail at all times for all the users
(c) never lose mail sent to you when the main server is inaccessible because of 1, 2, or 3.
Without a highly available setup and configuration, you can forget (a) and (b). The best you can manage is (c) by setting up a secondary mx server to hold your mail until your system is back online. The remote mx server can also be configured to allow users to send mail via smtp, but you'll have to set them up with a different mail configuration, to allow that. Most users will have difficulty understanding using "different profiles depending on circumstances" so that won't be as easy as you think.
If you get a second dynamic IP for sending mail will tend to get your mail blocked as spam if you send from it directly. However, you can use that line to forward mail to the secondary mx server and allow that server to send on your behalf as long as it's configured with some kind of authentication.
For users of your exchange server, if you lose network connectivity, they won't have access to their mailboxes. Nor can you set up a "backup" mailbox easily, unless you have another internet connection they can use to access the server (dynamic ip is fine for this).
...
So, here is what I might consider doing if "cloud" is not an option
exchange server hosted in the office, preferably with redundant network connections and a good firewall for handling multiple connections (I like
pfsense). EFA hosted with a VM provider and configured as the primary MX, with the fixed IP for your exchange server configured as a secondary MX (or secondary EFA in front of the exchange server as secondary MX). Then use a fixed ip line, and a dynamic ip line from different providers.
exchange server configured to use primary MX host in cloud as smart host
scenarios:
i) primary mx host down? exchange server reconfigured to send via secondary mx host (locally host efa) via the fixed ip line. secondary MX record means mail is sent to your secondary mail server instead ( to the machine listening to the fixed ip line)
ii) fixed ip line down? don't care - mail goes out to the primary mx host via the dynamic ip line. if you set up dynamic dns, the your owa.*.tld and mail.*.tld domains will still resolve to the dynamic ip line (they should resolve to both fixed and dynamic). Worst case, you update the dynamic host records to remove the fixed ip line by hand. Thus users can still access their mail on your exchange server.
iii) dynamic ip line down? don't care. everything still works. worst case, remove the dynamic ip record from the owa|mail.*.tld domains
iv) secondary MX (local efa) down? don't care. just point your firewall at the exchange server instead of the efa box until problems resolved and live with the temporary increase of spam
v) exchange server down? you're fucked. go home until the problem is resolved, or avoid this by getting a highly available exchange server setup.
vi) both internet lines down? you're fucked. go home until any connection is restored. consider getting a third line in the future like I've done (yes, I've had two lines down at the same time)
The only real problem is maintaining two efa instances. It'd be nice if two instances could share configurations so you only have to configure one.
At the end of the day, if you don't have redundant internet connectivity for your locally hosted mail server, there is not much you can do.
