Settings > Applications > Manage Appications > Speech Input
At least I think it was called "Speech Input". It took me ages to find as well!
It was called Voice Search. Thanks. I looked at the applications and sorted them by size and assumed that would be it.