The connection to Microsoft Exchange is unavailable. Outlook must be online or connected to complete this action.This error can occur when you get names wrong in your internal or external URLs. So, I verified the names in all of my internal and external URLs. I also tested connectivity in Outlook and the URLs from Autodiscover were correct. Also verified the names in the certificate.
It turned out to be an issue with the default gateway. As part the connection process, Outlook 2016 was attempting to connect with the default gateway (which didn't exist on my test network). When connectivity to the default gateway failed, Outlook provided that error.
To fix this, I pointed the client running Outlook 2016 at a valid IP for the default gateway. I used the IP of my domain controller. It's not important whether it's a router or not, it just looks for an IP that is alive. I've been too lazy to put a packet sniffer on it yet. I'm just happy it's working.
Short version: Make sure clients running Outlook 2016 have a valid default gateway.
Note: Credit to Stan Reimer who actually gave me the fix after it was discovered during development of a Skype for Business course
Update: For an explanation of why this happens, see this post: http://blogs.technet.com/b/rmilne/archive/2014/03/27/outlook-unable-to-connect-to-exchange-_1320_default-gateway-not-found.aspx