Your basic quest idea is absolutely no problem - but to give them randomly and conditioned to available maps is a more tricky part.
First, you would need one key item "letter" for each possible destination, and each destination adress should have an event that reacts to that specific item, removes it from your inventory and adds +1 to a variable "letter delivered".
For each post office, you'll need an event that activates a switch "delivery active" to prevent additional quests until all letters have been delivered (if you allow for several such quests at the same time, you'll need more variables, more switches and need to be very carefull about your event logic).
If that switch is off and you go to the post office, it decides on the number of letters needed and stores that in one variable, then activates a common event that hands you that umber of random letters.
If the switch is ON, then it compares the variable of delivery needed with the variable of delivery done, and either sends you to continue or gives the rewards and deactivates the switch.
Now the tricky part is the common event giving you the key items "letters".
It needs a counter and loop for the number of deliveries needed, and for each letter randomly selects one of several possible letters.
And the "possibility" of a letter is conditioned on switches for explored areas - those switches would be activated whenever you enter a new map, which means you need a lot of switches for this, and the conditional branches would be very long.
So yes, it is possible - but a lot of work, and you need to prepare for it before making those maps...