Chinese input using New Phonetic Method actually does this too. Basically after I type the sounds then tone and move on to the next character it will change the first character based on the sounds and tones of the following characters and continue to do so onto I press enter. Often I will type out an entire sentence before pressing enter, though sometimes it starts to spit out bad results if you go for too long. It also does some recognition based off previous character choice such as when using gendered pronouns, which I would assume the speech recognition they are claiming would have a lot of trouble with as the pronoun in speech is the same for all genders, such as the word you, or s/he/it.
On the iPhone they go one step further with a slightly different form of input where even the tone is not required unless you are having trouble finding the correct character. I can start typing just the sounds of multiple characters strung together and the suggestions bar will show possibilities. Going a step even further, my Taiwanese friend showed me that you don't even have to type out all the sounds, just the beginning sound is enough, so I can type out an idiom by merely pressing the first phonetic symbol of each of the typically four characters. The problem with these latter methods is training to know which words can easily be found by omitting the ending phonetics and which cannot.
I'm assuming Baidu is probably doing this for Simplified Chinese rather that Traditional, though it would be great if it could do it for both.
The largest problem still remains, most likely, with bilingual input. Typing I can easily switch between typing Chinese and typing English, but speech recognition has so far not offered this option. At my inlaws house conversation can easily go from Mandarin to Taiwanese, with random English words thrown in within the same sentence and not missing a beat. Humans have no problem being able to recognize the meaning of these kinds of sentences if they speak, or at least understand, all three languages. Even a basic understanding isn't necessarily required, as is the case with English in this situation there tends to be certain words that everyone understands without having any ability to speak any more of the language.