We prove that optimal traffic plans for the mailing problem in Rd are stable with respect to variations of the given coupling, above the critical exponent α=1−1/d, thus solving an open problem stated in the book Optimal transportation networks, by Bernot, Caselles and Morel. We apply our novel result to study some regularity properties of the minimizers of the mailing problem, showing that only finitely many connected components of an optimal traffic plan meet together at any branching point.