I've had luck with digital ocean by sending friends emails (who have accounts at major providers) and having them mark it as not spam a few times over the course of a week or two. After that, it worked without issue.
It is definitely possible to get it up and running, but there's often problems due to entire ranges having bad reputation. There was a gigantic thread about it in the Mailop mailing list last year. If you have access to it's archives then it's definitely a worthwhile read (and entertaining too!).