How to troubleshoot "okay google everywhere" missing from voice settings? This is what I see:

(Click image to enlarge)



And this is what I would like to see:



I am using Motorola Moto G 3rd generation (2015), 1 GB RAM, 8 GB storage; XT1541

I have already tried a few things:


I'm already using the latest version of Android as of now: 5.1.1 Lollipop.
I'm using the latest version of the Google now application: 5.1.17.19.arm
I have tried to search for the magic phrase "okay Google everywhere"
I have tried to uninstall and reinstalled the Google application. I think it was just a downgrade to version 4 of the app because the Google Play store told me that it is a built in application.
restarting the Google application by force quitting the app and/or restarting the whole phone.
switching the local from UK English to US English wherever I could find it in the phone settings.
and maybe some other things too.


But nothing seemed to help.

What could be causing the missing option? What else could I try to make it show up?

I am also thinking about contacting support. If I do so, should I be contacting Google or Motorola?

Edit:


The version of my "Google Now Launcher" application is 1.1.1.1706998
I have even tried factory reset with and without restoring from backup; no success.
Go to https://www.google.com/settings/accounthistory/audio and turn on voice searches and commands.