Casey Chesnut has written a client for the Pocket PC Phone Edition that records your voice, shoots it off to a .NET Web Service running a speech recognition engine, and returns the results to your client. The best use of this is certainly for constrained input, not continuous speech recognition. Is there a killer app? The one that comes to mind is hands-free routing: a GPS still costs a few hundred bucks and inputting a destination is a pain, especially when driving. "I'm at mile 200 on route 50 in Nevada. How far to the gas station?" would be a pretty cool thing to be able to ask your phone.
Delightfully, Jakob Nielsen's latest Alertbox argues that voice interfaces are poor choices for the majority of applications. Compare and contrast.