I have a test message 15th October, but my Android email clients (Gmail, Outlook) cannot find those messages. It really causes problems. I waited a few minutes for the results, so the computer power should not be the problem here. I can search the messages in my Email client Evolution in Desktop Debian, but not by my phone.
Email settings: IMAP and never deleted/archieved the message in any system
OS: Android 7.1.1
Phone: Oneplus 3T