From the Super Mario Wiki
The Wandering Nomadimouse is a Nomadimouse that resides on the path of Dry Dry Desert. He appears in Paper Mario. To escape from the extreme heat, the Wandering Nomadimouse stays under the shade of a palm tree. A letter on a roof in Dry Dry Outpost is for the mouse. He'll give Mario a Star Piece if the plumber delivers the piece of mail to him.