There's also an item yo can put the map in, and get its actual Latitude and Longitude.
From there, you can find the area fairly easily, so that the map is in a 12-15 step (per side) square. Even without mining, you can take a step or two, dig, repeat, and find a chest fairly quickly.