I agree this is annoying, however, note that search within your PMs works fine if you want to find a particular message. Try initiating a search from the messages tab on your user page – there is a checkbox for it – or view the search help.
Longer term we do need a way of segregating out all the thousands of welcome PMs…