+1 for SPF on my domain, did exactly the same, was able to send without any 5xx errors.
Also stopped getting the bounce back spam emails for my domain into the domain bucket email account
Yeah, like I said we was like [censored], we even tried DKIM where we would hash up the email, but then realised that would only help to detect if anyone tampered with the email etc.
But with SPF that is saying that the reverse domain lookup for the actual IP address of the server that is doing the actual sending of the email is allowed to send you emails.
So the OP will have to set up one or two DNS records for the domain of the server that is sending the actual emails i.e. the reverse lookup of the IP of the server, then a DNS records for each domain that is having the emails being send by the server.
But yeah, that sorted our email being flagged as spam, as well as stopping the 5xx error codes and now none of our emails are being stopped.
For my Game Dev Stuff which contains certain information I then Hash some of the email fields that I don't want the man in the middle or 3rd parties to alter using DKIM.
So end result, I am happy, our users are happy and our users that we host web and emails services for are happy
Paul