I didn't read every post here but this is what I would suggest if anything (if it's already been said disregard me then).
Keep Treasure Maps the same as they are.
Add a rare/ultra rare key that can drop during -any- level of difficulty of map. Make the key no-rent to discourage the looter from keeping the key for a later date or time. The key looted should be on par with the same level of difficulty that the map was.
The instanced zone would be one of say 5 or 6 random zones, each with it's own flavor/design/mobs etc. Each zone would be a typical dungeon crawl and have all of it's own named and drops etc. Maybe at the end there is either a treasure chest or a boss. Maybe even make 1 of the random zones lower on the random scale which is a bit harder and has more reward, to make it even more prestigious.
Each instanced zone should only take on average less than 2 hours to complete, to encourage people to get in on a treasure map group for the chance that the key would drop, and have the time to complete it.
There should be a clicker of some sort at the end of the instance to zone out. The zone should have a timer of, say, 5 hours, to allow ample time to complete it in case of a wipe or link death etc..
Now, assuming something like this is done, treasure mapping will become increasingly popular and eventually people will get tired of the same old tmap loot and might be discouraged to join in on the fun, so add something like an experience scroll as a drop which can be clicked to gain experience based on the difficulty. This will encourage people to still join in for a chance at a good chunk of experience at the end.
Anyway, those are my thoughts on the subject.