I know everything about mail such as who sent it, what was it about etc. but it was not in "all mails". I even searched in the search icon with enough data, but still, I could not find it.
If there are no other labels attached to the message you have a few options.
Find any email from that person, open that email, click the three vertical dots, and select "filter messages like this". You should now see all messages from that person.
if you have a lot of emails from that person you can add to the filter to include a key word, or a date range.