You could run your own Fediverse server.
Can you do one search on one server, and find any email address that exists anywhere? (not that I know of)
Can you send email regardless of what server the email lives on? (with some exceptions, but mostly yes)
Federation is not infinite or unlimited, so no, there is no "one search to rule them all" within the confines of a single instance. (But then there's no way to access all email, or search all email addresses across mail servers to find someone.) Still if you're on an instance, and go out and find people on the internet that interest you, regardless of how you find them or what instance you are on, you can follow them, and their content will begin to be federated into your feed, on the instance you use.
The server you choose matters, but it's also not something you can't change. (Like getting a new email address.) If you use Gmail, but someone uses a mail server that has been blacklisted because of bad players using a domain name or IP address, you probably can't get email sent from those servers.
But initially, you can either go with the biggest instance, or the first one you see on https://joinmastodon.org/servers that seems fine and then try it out for a while. It's not a single decision you have to make for the rest of your life. It's just something new, and a new way to have access to some people connected to each other through some instances, topics, follows, etc.