I've a small SaaS where each client gets a subdomain (stackexchange.my-saas.com)
I've a mailgun account where my main domain is setup and I've created a wildcard SPF record in my DNS and if I add additional domains to my mailgun account with a subdomain, they all verifies correctly.
My question is, do I need to add every new clients subdomain as a new domain in mailgun when I have the wildcard SPF record set or can i "legally" just create a from-address for each new client so the header of the emails will be from: Stack Exchange On My SaaS<[email protected]>
For sending, there is no need. As you point out, you can have the SPF records set so your email can be sent From: whatever subdomain. Note however that Mailgun will add a Sender: header with your Mailgun registered address if your specified From: address has a different domain.
From: Stack Exchange On My SaaS <[email protected]>
Sender: [email protected]
For receiving emails, it's a different story. This is a Mailgun limitation and has been answered in this other question.
Basically, Mailgun uses the same MX servers for everybody, so when they get an email they need to look up to which customer the email belongs to, much like any regular multi-host mail server.
(UPDATE) They allow to register wildcard subdomains, combined with a wildcard MX, it might just work for every subdomain. Note however that because of how DNS works, there is no standard way to define BOTH a wildcard MX and a wildcard CNAME in the same domain. CloudFlare is currently supporting this but it will fail for most other DNS providers.
Alternatively, for receiving emails in your SaaS, you have to register each of your subdomains with Mailgun independently (possible through their API). Note that this also implies verifying the domains adding TXT records for each one on your DNS.