I have played obsidian for over a decade now, and I've gotten 2 treasure maps. Two. The whole time.
I suggest you increase drop rate by 50-100x. I'm not joking.
The loot provided by a treasure map isn't that great to begin with, but its something interesting/fun to do, it also gives more relevance to a cartographer.
I would scale drop chances to be much more common for lower level maps, and much more rare for higher end, however MUCH more common than they are now.