They pay 3rd parties to handle relay duties. A large chunk of reliable delivery is based on those received headers, aka what systems your mail is relayed through.
Postmasters at large ESPs and inbox providers can and will text each other to resolve issues.
This is pretty much how the internet works as well (BGP, etc). It's opaque, but open.