I remain convinced that somewhere inside of Mail.app someone decided to try to speed up search with some approximate index or badly rewritten strcasecmp.

Mail not being able to properly find an exact string match correctly means I had to give up and just use GMail in Chrome and on iOS. Once GMail on iOS added IMAP and SMTP, I never needed to go back.