How can I search for historic emails older than the default retention period on my Android tablet?

[AC Question]

I have a Samsung Galaxy Note Pro tablet and have a question about email. On my iPhone when I search emails for specific text, it will search my entire inbox. Sometime it gives me the option to 'search on server' rather than just the mail on the phone. When I do the same on the default mail app, I only see results from the last month (or however long I am keeping emails). I have tried the GMail app (but can't make it work for non-Gmail accounts), Aqua Mail and Outlook apps, but see variations on the same result, i.e. it never stops searching or returns 'no results'. I have spent many hours Googling this and can see I am not the only one with this problem but cannot find a solution. I can't believe it is impossible, since the iPhone and iPad can do it. One result I did find is that one Outlook for Android update fixed this problem, but it still seems to be broken to me!
Does anyone have a solution for this?
Thanks