The term I immediately thought of is "postal service".
I've never heard it used to cover electronic mail and it scores higher in Google Ngrams than all the other terms, and it wasn't a newly invented term after the rise of e-mail. Also, it's perfectly formal.
One minor drawback is that it surely won't work as a drop-in replacement in all possible uses.