My company was in a similar boat with a decade plus old domain (though I don't think it ever had anything scummy associated with it before we bought it). When

My company was in a similar boat with a decade plus old domain (though I don't think it ever had anything scummy associated with it before we bought it). When we first started testing our site in January '09, our "click here to verify your email address" emails were going to spam, and it was a major bummer. After a week of calling ~100 of our friends with @gmail accounts to sign up and mark the email as not spam, our messages finally started going through. I have no idea if that's a normal sample size, nor any proof that that's what made the difference. Regardless, I strongly believe that having lots of people go to their spam folder and mark you as not spam has a huge effect; if I was designing a spam filter I'd definitely weight that feedback heavily. If you can somehow build that into your app (i.e. make people verify their email to continue), in the long term it should solve your problem. In the short term, your UX will be a little worse and you'll be constantly wondering how long it's going to take until google trusts you. Welcome to the nightmare that is email deliverability!