I'll agree on the "they're pretty good" bit, the treasure map - chests are great, the trader quest stashes are mostly about the quest progression.
How can you find them easily? Find the center of the area. Right outside the range when the icon starts to blink, you can either just aim with the icon from two angles, or slap frames on the ground where the icon swaps. The treasure used to be very close to center, not entirely sure of this patch, but usually within 5 meters of the center.
Focusing your efforts on the center will usually cut your digging area by something like 60-80%.
They're always under two blocks. If it's two blocks of water, it's on the bottom of the lake; if it's two blocks of a POI, it's usually under a roof. Most often it's two blocks of dirt, and then at worst a mountain side is confusing since it goes up and down pretty rapidly.
Once you've found the center, instead of excavating the whole neighbourhood; an easy way for good coverage is to dig parallel trenches. If you dug one already, you can dig another three blocks over, leaving two full blocks in between - you don't need to see the same block from two sides.
That'll save you 2/3 of the digging.
Depth will need to vary by the deepest side, you'll need to see the third block below every block you leave untouched.
If you want to optimize your digging even further, you can dig in a .. "chess knight" - like pattern. Two up, one to the side. That's still about half the trouble of digging trenches, but may get quite confusing especially on a hill.
Code:
oooooo oo1ooo
ooXooo o1X12o
ooooXo o312X2
oXoooo 3X342o
oooXoo o34X4o
oooooo ooo4oo