If you've got a world populated by multiple different sapient species, and that world has a postal service, chances are the mail delivery will be handled by a species capable of flight. If the postmen themselves aren't flight-capable but use mounts that are, that's this trope, too.
This trope practically justifies itself; after all, if you need to task someone with mail delivery, why not pick someone who can fly over all the ground hazards and easily land at each mailbox?
Particularly common in Ocean Punk settings, since the lack of land magnifies the advantages of flight.
Can be a form of Mundane Utility. Compare an Instant Messenger Pigeon, which is not officially a sapient species but often gets the message there as efficiently as if it was. If you're comparing this trope to Flying Dutchman, you're probably reading too quickly.
- The namesake of Kiki's Delivery Service is a variant, where Kiki is a witch who makes deliveries via Flying Broomstick.
- The Pokémon anime has Delibird's Delivery Service and Pelipper's Post Office. Other than being from two different regions, think of Delibird's Delivery Service more akin to UPS while Pelipper's is your standard postal service. Another episode had a "Carrier Pidgey Express" parcel delivery service.
- In One Piece, newspapers are delivered by trained seagulls all over the world, due to the huge amount of oceans and island. Furthermore, we later see that the Revolutionary Army seems to use large crows to deliver messages, and the World Government has been seen sending messenger bats to people.
- In Aqua/Aria, Woody is an airbike courier. This series also has the land-based, or should we say canal-based Mr Mailman as well.
- The My Little Pony Friendship Is Magic fandom is somehow overwhelmingly in agreement that the fan-favorite background pegasus Derpy Hooves is Ponyville's mailmare. If we tried to list every fanfic portraying her in this role, we'd be here all day.
- Plan 7 of 9 from Outer Space. Our heroes have their luggage delivered to Antarctica by rocket mail, but a targeting error means it wipes out half of Melbourne instead.
"I knew I shouldn't have packed that plutonium-powered toothbrush!"
- In the Discworld of A.A. Pessimal, the Air Mail has largely been a monopoly of Klatch and its (now) civilian-orientated force of magic carpets - which now offer an unparelleled passenger and airmail service linking the major cities of the entire Disc. It has not been lost on Lord Vetinari that the klatchians made a kind offer to ferry the diplomatic bags of Embassies to and from their home capitals - for a modest fee and a promise the diplomatic secrets will not be interecepted or tampered with while in transit. Vetinari's riposte was to offer the growing Pegasus Service as Ankh-Morpork's airmail equivalent.
- In the Harry Potter series, owls are used to deliver mail. The Ministry of Magic uses enchanted paper airplanes for internal memos (although MACUSA uses origami mice instead).
- In Cold Copper Tears of the Garrett, P.I. series, a description of the multi-species crowd in a TunFaire neighborhood includes a mention of a winged pixie messenger.
- A bird postman (postbird?) is the second animal (Mudge is the first) Jon-Tom meets, back at the beginning of the Spellsinger series.
- In the Vorkosigan Saga it's mentioned that in rural areas of Barrayar, mail is distributed by lightflyer (small plane) pilots who deliver the post to regional drop locations. They replaced horsemen who used to deliver the mail to the various individual's actual homes (Though Count Piotyr was deliberately slowing down the transition so that all his couriers - many of whom were former cavalry officers who served under him through multiple wars - would qualify to retire with full pensions before being laid off).
- In A Song of Ice and Fire, maesters use ravens to deliver messages back and forth. In particular, the Wall will send a white raven south to signify the beginning of winter - this occurs at the end of A Dance with Dragons.
- A short story by Rudyard Kipling, With the Night Mail, chronicles the adventures of a transatlantic mail airship.
- The Secret of the Ninth Planet, by Donald Allen Wollheim. While on an expedition in the Andes mountains, the protagonists receive a special delivery by missile post. The missile, radio-guided from a Moon base, flies overhead and detaches its message-carrying nosecone which then floats down to them by parachute.
- Hermes, the Greek messenger god, has winged shoes and a winged helmet.
- In Shoe (a world populated by semi-anthropomorphic birds), Loon is a mail and general delivery flier.
- In Warhammer 40,000, the most reliable form of Dark Eldar communication is the Scourges; denizens artificially modified into Winged Humanoids. Gives one the closest thing to Diplomatic Immunity one has in the Wretched Hive which is Commorragh, provided they can survive the operation and avoid the natural hazards.
- BIONICLE: Venom Flyers were used to deliver messages between the Brotherhood of Makuta and the Dark Hunters.
- In the Paper Mario series, the postal service is run by Paratroopas. You can get one of them as your partner in the first game.
- The Rito people of Dragon Roost Island in The Legend of Zelda: The Wind Waker.
- The Pokémon Mystery Dungeon series has Pelipper (A pelican Pokemon) delivering the mail in each game.
- Pete the pelican from Animal Crossing.
- A pelican is responsible for mail delivery in Legend of Mana, and figures into several sidequests.
- Solatorobo: Some sidequests make you the mailman (with a unique flyer), though it plays out more like a racecourse.
- There is no GATE; we did not fight there: For the marching cohorts of the armies of Rhavenfell (and possibly the rest of the Empire), messages are carried via ravens. Couriers for actual mail in the Empire proper can be handled by anyone, but the use of Harpies, who can fly, is slowly growing more popular in Rhavenfell due to their alliance with the humans.
- Carrier pigeons can be seen as a downplayed example.
- Amazon.com may soon be using cargo-carrying unmanned aerial vehicles to drop off packages for its customers.
- One of the first (some would say the first) civilian uses of airplanes was carrying mail from city to city. This was at its peak in the 1920s and 1930s; it declined due to companies scamming the government due to poor oversight, and a large number of military airmen dying in plane crashes in poor winter weather when the US Army tried to take over all air mail responsibilities while lacking in sufficient experience in night time and winter operations, as well as poorly equipped aircraft and insufficient manning, due to Great Depression-related budget cuts.
- Rocket mail has unfortunately been more effective as a publicity stunt than an economical means of mail delivery.