Mail.app Search Indexing - How does it work?

I believe that Mail.app uses Spotlight to search content on emails that are stored locally on your computer, unless something's changed recently. It uses a separate system to search header info, and kept that info in something called "Envelope index" in Mail Data in the Library somewhere.

Whether "every single" email you have is stored on your provider's server depends on the vendor and how you've set it up. If you keep everything on gmail, for instance, you can search back as far as you like. And Google's search engine is pretty quick.