On the new shield TV remote I've tried using the voice search and it's god awful. Trying to say simple stuff like "House of cards" doesn't work.
I've tried at least 20 times and it hasn't once detected what I'm saying correctly. Sometimes it will pick up the first word and then just wait. Other times it just picks up a garbled mess.
The controller is a different story though, it seems to work just fine and the accuracy is great. I don't know what's the deal with the remote.
I was having the same problem with my Nexus Player, until I realized that the remote batteries were too low. Check that?