How to recover domain name from previous bad SPF record?

Question

TL;DR: We had SPF too permissive (+all) and spammers used this to send tons of spam "from" our domain. We restricted that to ~all and added DMARC (not DKIM though), now other providers do not trust our real emails. How to make them trust our domain/SPF record without making it too permissive again?

I've worked for this company for awhile now. However the DNS management is done by other people.

I've noticed that our SPF record was pretty bad (literally +all at the end) and the people who manage DNS argued that this is needed since many servers send automatic weekly/daily reports. However on close inspection they do not use our mailing domain name. So I suggested to fix SPF record to have at least ~all at the end and add DMARC record to receive reports of messages that are considered spam. We could not add DKIM as there are multiple systems that require sending emails (all proxied via GMail servers with their smtp-proxy servers).

Once we have done so we started receiving large numbers of reports about spam messages with our domain name as sender. All of them do look like spam and definitely not sent from our servers.

Obviously this is what we wanted to achieve, but now I see that our legit messages are sent to spam as well, even though all sending servers are added in SPF (we use Gmail for business).

Q: How can we recover from this and make other providers trust emails sent by hosts in our (now valid) SPF?

UPD: Below are examples of SPF and DMARC records we have:

v=spf1 ip4:xx.xx.xx.xx ip4:yy.yy.yy.yy ip4:zz.zz.zz.zz include:_spf.google.com ~all

v=DMARC1; p=none; rua=mailto:[email protected]; ruf=mailto:[email protected]; sp=none; fo=1; adkim=r; aspf=s

Answer 1

1. DO DKIM for each legit sender. Is it done for all the senders you show in your SPF record?

2. Change the ~ALL (softfail) to a -ALL (hardfail).

3. When you're confident you've authenticated all legit email and have had p=none for a while and the reports aren't showing legit email as not authenticated, then graduate from p=none to p=reject. This will make your email authentication have teeth so to speak, as inbox providers will actually start rejecting non authenticated email.

Once you've changed to p=reject, it's important to make sure you are really good about keeping your email authentication up-to-date, meaning if an IP address changes or you change providers or whatever, it's critical to edit your SPF record and also set up DKIM.

This will help you clean up your reputation as spammers and scammers will no longer be able to spoof your domain name. That will help start to rebuild the rep because spammers will no longer be ruining your domain name by sending awful messages with it.

Outside of email authentication, you can also make sure you're using best practices for email. For example, do you do email marketing? If so, do you do double opt-in? Do you periodically sunset email addresses that have not engaged in a certain amount of time, say 3 months or 6 months, so that you're not sending to people who for whatever reason never engage with your emails.

Check all the IP addresses you send from for blacklists and so on and, assuming you've cleaned up the practices that got you on the blacklist, apply to be removed. If it's a shared IP address that's on blacklisted on serious blacklists then you may need to talk to the ESP about the shared IP block you are on.