In regards to understanding voice input, I have been thoroughly impressed with Google's ability to do this ever since I started using their 1-800-GOOG-411 service. I didn't get my first smartphone with data until 2009 (Droid), so the service was really handy for me before that. I'm sure it also gave Google a ton of data to help them improve their capabilities (even mentions that in the Wikipedia article [1]).

http://en.wikipedia.org/wiki/GOOG-411