This thing happens sometimes, specially if you use a shared hosting. Recently using a well known cloud provider the Public IP address assigned was in a spam blacklist! It’s a good idea to have a look at your IP and domains frequently.
(Disclaimer: I’m the founder of the tool used for the lookup in the blacklists)