Search on server support with Gmail has been broken for me for about a year. Have others experienced the same? I was surprised to find almost no questions of this sort when searching on Google.
My experience is that if I search for a specific message by subject that I can find in Gmail web, it returns no results using Thunderbird search, with search on server checked. If I search for someone I email with a lot (my significant other), I only see emails since the start of the year (note: this is basically the emails I have synced/downloaded - the first 1000 emails in All Mail)
I am searching for emails in “All Mail”, with Run Search on Server and Search subfolders checked.