Got a few hundred PM's in my inbox/outbox, have seen other users saying they have thousands, need to be able to search them, unsure why the main vB code doesnt' support it but, at least a hack should be out there for it. I searched, didnt' find this requested or asked about even which suprises me, but it is mentioned on vbulletin.com...
I dont think its easily doable or I'd guess we would have added it in by default. I think the way the system currently works will not allow for easily searchable content.