'moved over to a newly-registered domain"

Was this new domain in use before ? If yes, check if the domain itself was blacklisted earlier. Sometimes, domains are used for scam/spams and then someone else registers it only to find out that google is blacklisting it.