Has the IP address of the server changed? It might me that the server needs to warm up before the mail is seen as legitimate.
If a server is starting to send a lot of email from an IP address that it does not know, you are having more problems with spam tagging. Make sure your SPF records and DKIM are correct and that you don’t have some weird config with that. Also check the contents of your email and see if you are not on any blacklist.