I'm struggling with this issue as well. Sometimes when I'm traveling, I'll be in an area with no data connection or WiFi. I can say "OK Google" to activate the voice search...however, any command I give it (i.e. Play 'artist') is met with "Can't reach Google at the moment. You can still use the mic to place calls. Say "Call" and a name or number." I know the offline voice recognition works, because I can turn off my WiFi and data and use the voice input to write text. I have Xposed installed and I tried the "GoogleOfflineVoice" module, but I'm still met with the same message.
Does anyone have any ideas of a work around for this? This is particularly frustrating because I used the Google Search API and Tasker to automate a lot of my phone usage while I'm in the car. However, if I don't have a data connection, it no longer functions.