Android IMAP client with working search option

OK, so far I've tried Gmail, K-9 and BlueMail email clients. I can correctly setup my IMAP server, and I'm able to send and receive emails. The problem is when I try to search for an old email I received maybe a few months ago. Gmail and K-9 return nothing. BlueMail returns and error. My mail provider is JustHost. As search is working under the web mail service, they say the server hasn't got any problem. Is there a general issue in IMAP search? it's quite frustrating not been able to search my mails from my phone. My device is a Nexus 5x with android 6.0.1