Could be case by case, or buggy, or perhaps not fully implemented yet in the beta phase. For now it seems like it might be limited to what's loaded in the message view initially before you use "Load More Messages". So if you have a lot of messages just from today with a particular contact, then those will probably be the only ones appearing before you have to use "Load More Messages" to get more messages. But, if you don't have that many--like I have some where I have a couple of messages with someone from yesterday, then a few more from 3 days ago, then one or two from a few weeks ago--those show up even before you have to use "Load More Messages", and those seem to be directly accessible from a search.
It seems like they've improved this in iOS 7, although perhaps to a limited degree. Perhaps they'll expand in the future, or perhaps this will be it (which I guess is still somewhat more than before).