Woohoo!
The issue was with my IP. Once I changed IP’s everything worked. So ya, it was a blacklist problem.
P.S. so you guys know, Yahoo.com rejected mails from me after I changed my IP even though I’m not on their blacklist server, but I don’t think my dns changes had time to propagate.