Strange one here.
We needed to send from a new domain.
Followed steps as usual - I can see DKIM and SPF are verified.
Worked fine for a couple of months, now all of a sudden the emails are hitting the Spam.
Anyone shed some light on this?
Well, SPF and DKIM help are important for ensuring a good email deliverability and inbox placement rates but they're not the only ones responsible for your inbox placements rates, deliverability, etc. You'd need to follow and adhere to the best practices while sending out the emails on a daily basis to ensure that your email domain and IP remain in the good books of the ISPs and email filtering companies. Has your email volumes been fairly inconsistent lately? Has your email engagements been constantly dropping? Are you hitting too many spam traps? Have your emails been marked as spam by a lot of recipients recently? Is your email domain been blacklisted? There could be more than one reason as so to why you're seeing elevated spam rates, there are a lot of moving parts here. You may find linked threads in this thread useful.
No - all you have listed checks fine on our side.
I even ran a test with the same email using a different domain and that worked fine.
It seems to be this particular domain.
Well, there's something happened lately that may have degraded the reputation of the domain because of which they're not landing in the primary inbox and are categorized as spam (did you encounter a lot of bounces recently?). Also, there can be more than one and many factors playing simultaneously in determining the email domain reputation. And, not every email filtering logic works the exact same way, i.e., emails from a particular domain may end in the spam folder for say gmail, but that doesn't guarantee that they'd also be classified as spam by say outlook.