Important!
Based on customer feedback, we’re making a few changes to the plan to roll out the extension for Microsoft Search in Bing. Based on these changes, the rollout will not start with Versi...
Updated Feb 11, 2020
Version 3.0
Blog Post
3 MIN READ
Introducing – and Managing – Microsoft Search in Bing through Office 365 ProPlus
The ADMX files does not seem to work if you are using Server 2012 R2 or below. I can see the 'Microsoft Office 2016 (Machine) folder and some policies but not the one relevant for this. So does that means companies who haven't upgraded to 2016 and above has no option? This is getting ridiculous. 
This is what the installation instructions says:
This download includes the Group Policy Administrative Template files (ADMX/ADML) for Office 365 ProPlus, Office 2019, and Office 2016 and also includes the OPAX/OPAL files for the Office Customization Tool (OCT) for Office 2016.
Update: Okay so it seems this is because I used the 64 bit download of the GPO. When I copied the files from the 32 bit download, the setting shows up. Server is 64 bit so didn't think much of this. Hope this helps anyone coming across this.