The Deputy Postmoogle will only show up if there are any new quests available to you.
The thing that a lot of people seem to miss is the fact that some of the quests have prerequisites. The quest most people have a problem with is Thwack-a-Mole, which requires you to complete a chain of sidequests in the Central Shroud starting with Fungal Frolic