For Horde players, if you have a WoD L3 Garrison, and a large mount, you can position it half-perched on the roof of the Bank hut, on the side next to the mailbox. Change the view to look at the front of the bank. Voila, you can reach both GB and mailbox without moving.
For Alliance, I suggest Darnassus, as it’s a few short steps between mailbox and GB. Speak to the Bronze dragon Sidormi(?) on Darkshore to switch it back to pre-tree burning phase. Or BC banks in Shattrath or Exodar if your GM has a speed boost usable indoors such as Shaman’s Ghost Wolf.