Re: Not sure how I can be using the search feature incorrectly... go to the list of messages, hit the search icon and it clearly states it will be searching the server.
You are doing it the right way.
Re: fastmail
I have an account there, just checked, it worked, found two messages from 2013 (waaay beyond what the app had synced).
Please note that the search bar has a button for "what exactly to search for" -- initially it's message text, and tapping it, cycles through that -> all headers -> sender address only.
If the above doesn't help, please capture the issue in the app's debug log as described at the link in my signature, below. You will need to enable "raw session data".