Have no fear, you can utilize Live Search for Mobile via SMS (Text Messaging). I'm not sure why this has not caught more attention, but I think it's a cool idea. I know a ton of people who have unlimited text message plans but don't have a data plan for their phones (i.e. can do mobile browsing). So, offering Live Search via SMS makes perfectly good sense.
Take a look at this overview. They show how to do a variety of searches. Text a query to 95483 and then get back an answer. Here's a short list of possibilities:
Quick Tip List: