same problem here with wife's phone. droid turbo. missing search icon in stock moto email app "motoemail". she uses this for her promary email account which is a verizon.net address.
installed gmail app and search is missing as well for the non gmail account.