Woohoo! Erik Thauvin has updated his Java SMS front end to work with Yahoo!'s new SMS Search service. W00t. You can grab the MIDP2 jar file here which you can send to your phone via Bluetooth, or hit Erik's site for more options.
I actually had mocked up an incomplete version of this app to show around Yahoo! before the SMS Search launch, so I'm happy that Erik has taken the time to do the full version.