This was the fix.

  1. Open SharePoint PowerShell as Administrator
  2. Run this Get-SPServiceInstance -All > Get-SPServiceInstance.txt
    1. It will export all Services to the text file un C:\Users\[Username]\ Get-SPServiceInstance.txt
  3. Find the GUID for the Search Service. It was c0220b13-8093-4240-91e4-8427a68e8c0c
  4. Run the following 3 commands
  5. $value = Get-SPServiceInstance -Identity c0220b13-8093-4240-91e4-8427a68e8c0c
  6. $value.provision()
  7. $value.update()
  8. Reboot the SharePoint Server.
  9. Check that the Incremental Search has started!