Dealing with transactional emails going to spam from an old domain name

We got a great five-letter domain name for our web app, but we're i开发者_JAVA技巧nheriting a legacy of spam being sent from that domain. And hence, Gmail immediately dumps all transactional emails into spam. This is just a tiny problem.

We're using SendGrid to handle our transactional emails and have them white-labeled to our domain. We're not blacklisted by any services.

What can I do to overcome this spam problem?

I'm not sure there really is that much you can do, other than making sure that your dedicated IP (Which SendGrid has probably provided for you) is continually building reputation.

One of the things I'm trying to figure out is if your domain gets flagged for spam once, is it possible to recover? I am hoping it is.