Outlook profile can be created and set to default by creating a simple batch file script that adds nodes to windows registry. To create new outlook profile for all the users, run the script on multiple systems through Group Policy.
In the below example we will execute as a user logon script, Group policy object GPO to execute when the user logon or start of computer.
Creating a batch file script to create a new Outlook profile
1. Open Notepad copy and paste the below code based on your Outlook version.
Outlook 2010
reg add "HKCU\Software\Microsoft\Windows NT\CurrentVersion\Windows Messaging Subsystem\Profiles\<name>"
reg add "HKCU\Software\Microsoft\Windows NT\CurrentVersion\Windows Messaging Subsystem\Profiles" /v DefaultProfile /t REG_SZ /d "<name>" /F
reg add "HKCU\Software\Microsoft\Exchange\Client\Options" /v PickLogonProfile /t REG_DWORD /d "0" /f
Outlook 2013
reg add HKCU\Software\Microsoft\Office\15.0\Outlook\Profiles\<name>
reg add "HKCU\Software\Microsoft\Office\15.0\Outlook" /v DefaultProfile /t REG_SZ /d "<name>" /F
Outlook 2016
reg add HKCU\Software\Microsoft\Office\16.0\Outlook\Profiles\<name>
reg add "HKCU\Software\Microsoft\Office\16.0\Outlook" /v DefaultProfile /t REG_SZ /d "<name>" /F
2. Save the file as a BAT file.
3. Give permission for the BAT file in the network location accessible for all users.
Create a GPO executing the script when a user logon or start of computer.
1. Log in to Windows Server domain controller (DC).
2. Open Server Manager and select Tools > Group Policy Management.
If the Group policy Management is not there, you need to install this feature. In Server Manager, select Manage > Add Roles and Features and follow the instructions. Just select the Group Policy Management feature in the Features step.

3. In the Group Policy Management window, find your domain on the left side menu, right click and select Create a GPO in this domain, and Link it here.

4. Enter the name of the new GPO and click OK.
5. Navigate to the Group Policy Objects container on the menu, find your newly created GPO, right click it and select Edit. The Group Policy Management Editor will open.
6. Go to User Configuration > Policies > Windows Settings > Scripts (Logon/Logoff) and double-click Logon

7. In the Logon Properties window, click Add, and then click Browse and select the BAT file created in the above section.

8. Click OK two times to save the change
You can now close the Group Policy Management console. The script will be executed for each user when they log in to their computer. When they try to open Outlook, the Outlook startup wizard will be shown.

The Autodiscover feature should no longer have a problem connecting to the appropriate New on-prem Exchange server or Office 365.