We recently moved our site and mail to a new host VPS with dedicated IP. But after the move we noticed a lot of our emails are being caught by spam filters and we were completely blocked by hotmail and outlook so emails to any hotmail address would bounce. I have contacted them and they said this IP was used previously for spamming.
What do we do now? I know we can build our reputation on the IP with time but it's effecting the business now. Is trying to get a new IP a good idea?