Waldo F. Sterling

From Muppet Wiki

Waldo F. Sterling appeared in The Wubbulous World of Dr. Seuss episode "The Road to Ka-Larry." Waldo is a courier pigeon, first class, for Her Majesty's Postal Service, Court of Ka-Larry. Sue Snue asks him to deliver an emergency postcard to an archer, to stop an out of control zeppelin. Waldo complies, but only after Sue sacrifices a one of a kind stamp to serve as postage.