iRealSMS allows you to search at least the 3.0 beta that you can download if you buy/bought version 2. Version 2 might also but I can't remember since I don't really use the search feature.
ETA: There is also 'SpotSMS' that will allow you to use the native apple search to search sms messages.