...the single most important piece of context information is this: You're holding a telephone.Most people don't know how to use their phone, and even if they do know how to use it, they mostly use it to make calls and (in the UK and Europe at least) send text messages. Nobody cares about MMS or, the holy grail of the 3G operators, video calling, and after the horribly broken first implementation, they don't care about WAP either.
I'm one of the few people I know, and I know a lot of alpha geeks, that use mobile data seriously. Do you know how I find interesting new mobile sites? I use my laptop. Most of the stuff turned up by the current generation of search tools is either trying desperately to sell me something, or is desperately broken.
If you want me to see and use your mobile site, put a prominent link on your normal website. Please don't use auto-detection as the sole method of figuring out that I'm coming from a phone or PDA, it mostly doesn't work. For instance my Nokia N80 advertises itself as "Safari" since it uses a Webkit based browser, and I'm not going to risk running up my data bill by loading your normal webpage on the off chance that you'll figure out I'm on a phone and send me a light weight version.
So yes, I need a decent mobile search, but not very often. I'm also not entirely sure if everyone else needs it or not, what's your target market here? Are you looking for the early adopters and alpha geeks, or the man in the street? If the later I think you're in for an uphill struggle, they don't even think they need mobile data yet, to them they're still holding a telephone, and considering what's out there I don't blame them.
Mobile search isn't the killer application for mobile data, there is very little out there to search yet, except an unending stream of sites selling ring tones. Build the killer app, and then figure out how to index it...
Update: I'm obviously poking the holy cow with a stick here because I've had a sack full of email today about this, so lets make one thing clear, I still think that the next big thing will be mobile computing. The desktop paradigm we all live with today is dead, but mobile search? That isn't the next big thing, it might be next big thing three or four iterations down the line, but first we need some content.