Here is a little trick. I am not sure how well this works but I think it is
worth trying.
Microsoft did at least one thing good with Windows Mail. Each message is a
separate file in the file system (your C: or whatever). You can use a search
utility that searches files, separate from Windows Mail. The main problem is
that the search might get confused by the HTML or the headers and any
messages with attachments would at least require extra time, but I think you
understand all that. If you open any of the files that are found, then they
would (should) be opened by Windows Mail.