Unfortunately, a lot of services try to block email originating from cloud providers outright. As you've seen, one of the biggest issues is "the past history" of these netblocks - before we had even purchased them! We're working to get this resolved, but in general these services are slow to change in these situations. We take spam originating from out IPs seriously, and hope that these list will be updated to reflect that fact.
I know it's an inconvenience, but your best bet at this point is to recreate your droplet in order to pick up a different IP.