Any way to add a search for the private topic/message feature?

Not happening in the stock code 7.x as is.
Might want to post in the suggestion feedback forum.
While you are at it request that new messages are opened on initial visit instead of scrolling to the bottom of the page or pages.

Another vote here for the ability to search private messages.

I agree, so I shall make it happen

I love you...