Why do some From addresses work and others get rejected
In general: you should NOT use a from address of a domain you do not control.

the smtp protocol does not care and you can send an email pretending to be whomever sender you want, but given how it has been abused by spamers, other protection layers were put in place (DKIM, SPF).

These basically white-list which servers are allowed to send emails on the behalf of a specific sender (domain). Each other server in the world can then look at these lists, and decide to accept or reject your email based on that.

So it's not a hard rule, and depending on what from email you put and to whom you send it and how the various email servers are setup, it will work... or won't.

And no matter what, it's likely that more and more domains will white-list what are the servers allowed to send on their behalf, and more and more mail servers will look at these list and reject "unauthorised" senders.

So consider an anomaly that you can still send as @me.com for instance, and that it will soon fail.

Use your own domain(s) for the from and do set up the needed dns records to white-list your civicrm server (and the other servers you use to send emails).

And yes, it's a bit of a pain to set up, I'd suggest you to use an external provider (sendgrid, mailjet...) to deal with that. they all have clear instructions on how to set it up.