Ok this isn't a complete answer, but your reference to Google's API got me interested (hadn't heard of it before - and as you said, Linux is not great at voice recognition, so I've never bothered) and it looks like something that could be cool.
The following script should (I say 'should', my computer here doesn't have a mic!) record a snippet, convert it, send it to Google, return it as text, strip the spaces from the text to format it as a URL (needs work no doubt, I've only escaped the spaces), and search Google for it via Firefox. I've not looked at a shortcut key yet, or a better means of stopping the record.
echo "Recording. Use Ctrl+C when finished your query."
arecord -q -f cd -t wav | ffmpeg -loglevel panic -y -i - -ar 16000 -acodec flac file.flac > /dev/null 2>&1
echo "Sending to Google"
wget -q -U "Mozilla/5.0" --post-file file.flac --header "Content-Type: audio/x-flac; rate=16000" -O - "http://www.google.com/speech-api/v1/recognize?lang=en-us&client=chromium" | cut -d\" -f12 >search_query.txt
sed -i "s# #+#g" search_query.txt
firefox -new-tab https://www.google.co.uk/search?q=$SEARCH
rm -f file.flac
Any suggestions on where to go next would be appreciated no doubt! I'll keep tinkering though..