The signing issue is apparently due to Steve Kondik, who creates "Cyanogen", using testing keys to put parts of the software together. Probably because he has no right to use Google's own keys. Whatever the reason, it's possible to install these updates anyway, just not through the Market.
If you have the android SDK set up on a windows or linux PC you can use "adb push" to manually place the relevant package file into /system/app on the phone. This overwrites the existing package. In the case of VoiceSearch.apk, placing it into the right folder is all that is required. The market sees the app as installed. Job done.
As for where to get the VoiceSearch.apk, you can check the xda-developer.com web site for chatter about what, where and how to get packages for things people are having trouble installing.
Or you can install it on a 'standard' loaded phone...and copy it off from there onto a modded one. These could be the same phone with different loads at different times to enable different functions. That is a simple matter of backup and restore.