I suggest they can be found anywhere at any time with equal chance or smaller as now and infinite times per one char. This way the special encs are tied to normal gameplay and don't need to be abused.
1) I don't like this idea, because then it's all about luck not exploring world map.
You can just walk around on one easy square until you find them all.
2) But also I don't like that they are in "static" areas now, same for every player.
Because once you know where they are... see point 1)
So my proposition is:
When a new character is created, squares with each treasure are randomly chosen.
So basically locations of treasures would be static, but different for each character.
Coordinates of treasures can be stored as local player vars.
Big town and ocean/coast squares should be excluded.
Increase chance to find it once you are on the right square, to balance it.
Make sure people with outdoors have higher chance, taking into account that they move faster so leave squares faster.