If you keep getting error when using XrmToolBox or any tools when connecting to Dynamics CRM Online 2016, use the org id instead of the instance name.
You can find the org id by navigating to Settings -> Customizations -> Developer Resources.
The bug is introduced in
Microsoft.Xrm.Tooling.Connector for Dynamics CRM online 2016.
Follow the issue on GitHub https://github.com/MscrmTools/XrmToolBox/issues/299.