I have experienced this and it is one of the main reasons I still keep an imap client set up. There are certain emails I need to be able to find and gmail does not find them. Claws Mail does. Personally this is a minor annoyance with personal email, but I would hope their commercial offering does not have this behaviour.
Another really interesting thing I've noticed in gmail relating to search is that the number of matches for a given search is approximate, which makes perfect sense if they're using some kind of probabilistic data structure. However, when the correct number of matching emails does become known, because you have gone to the end, the result is not cached even client side. This gives a weird effect when combined with pagination: you go back a page, and the number of matches changes to the estimate again despite the fact the actual number is now known.
Another really interesting thing I've noticed in gmail relating to search is that the number of matches for a given search is approximate, which makes perfect sense if they're using some kind of probabilistic data structure. However, when the correct number of matching emails does become known, because you have gone to the end, the result is not cached even client side. This gives a weird effect when combined with pagination: you go back a page, and the number of matches changes to the estimate again despite the fact the actual number is now known.