Email services for self hosters

So, I'm trying to set up a self-hosted mastodon instance, and of course this requires an email service. Self hosting one is not an option, because of anti-spam stuff, or so everyone says. The recommendations are to use services like mailgun or postmark, but there's one thing I don't really understand:

All these services require verification of an email to be able to send from it. For example, if I want to use noreply[at]mydomain.com with mailgun, I need to click a link sent to that address, which to me feels like a catch-22. How can I receive that email if I don't have the email service set up yet? Do I have to set the domain up with some private email service (protonmail, tuta...) first?

Any help is appreciated, I'm pretty new at this.

Edit: Alright, so it seems that Mailgun actually doesn't require this weird confirmation email, just dns records. The first one I tried, SendPulse, did. Postmark requires an email from the domain at signup. Hope someone else can learn from this.