Reproducibility: The search results are always consistent. However, since username changes aren't common, I don't have much info to go off of.
Repro steps: If you have a PM from a user, and they at a later stay they change their name, searching through your PMs for their new name will not show their PMs. However, searching for their old name will show all PMs, with the new name displayed.
Expected: Searching using the user's new name should show the old PMs (when he had his original name).
URL: Examples are available in my inbox, but I don't want to publically post the name.