Just to follow up on this issue: my method to resolve all of this was to finally sign up for a Google Apps account and to transfer all my domains to Google Domains. I realize how typical it is for me to run to Google for everything, but it's the best solution for me. There's good synergy here because in Google Domains it takes about three clicks to set up a dozen DNS entries for Google Apps. It even set up a DKIM entry, which should help fix some of my initial problems.

I just wanted to thank Tom, who went to extraordinary lengths to help me with this issue. He even looked through my DNS entries personally to see where things might have been going wrong, and gave me advice for how to fix them. Thanks for all the help, Tom. You definitely helped my understanding of these issues, and I'll be looking through the resources you sent me in order to learn some new stuff.