When my phone is not connected to internet, voice search is showing "Can't reach Google at the moment" message and voice search is not working. It is working perfectly with internet connection.
The settings shows that it has English(UK) and English(US) as two downloaded languages for offline recognition. I have an android phone running JellyBean 4.2.2 in it. I think my OS version and RAM size (2 GB) supports voice recognition as mentioned in this answer.
Any idea how this can be solved?