I've setup 2 mail servers in the past 3 years and can reliably deliver to Gmail and Hotmail.. AT&T can be a chore I've found, they have been mostly unresponsive, but very little of my targets host there.

The other option is to relay through Send in Blue, or Sendgrid or something like that.