We are also seeing this error with our cloud BC implementation (so to be clear, not an on-premise configuration issue)
Our O365 admins have restricted user's ability to install office add ins themselves
The Dynamics Office add in has been made available as an Admin Managed add in
But, launching edit in excel from BC still results in same error as Sam identifies
Trying to setup the Dynamics add in from excel with the Business Central url (with or without our tenant link included) as server does not work, server details are not found.



