I think you have done all you can do assuming your searches were of the entire mailbox.  If a copy to self filter or autofilter was at play then it might have ended up in a different folder.

Today I created, and thought I sent, a long email message to a friend. I was surprised to find though that the message was not in my "copies to self" folder. I then did a search looking for the subject of the message, but did not find it that way. Next I did a search on the recipient's first name, and again could not find the message. Finally, I tried sending a test message to a fake email account to see if I had inadvertently turned off the option to save a copy. And that test message did go into my "copies to self" folder. Is there anything else I can try to find a copy of the message I thought I had sent?

Just a quick update. I got a reply back from my friend, so there is no question the message was sent. So now the question becomes, why didn't a copy of this message go into my "copies to self" folder at the time it was sent?