Ok, here's my method that I adapted from something I read on Stratics a long time ago:
Start by getting a general idea of where the location is. I usually try to line up two landmarks (such as a tip of an island, trees, inlets from the water, etc.) in UO Auotmap or even just the mini-map. One should be north or south and the other east or west so you can draw an imaginary line zeroing in on your pen.
I will position myself slightly above and behind where I think the pen is in westerly manner. I will throw a bandage or other marker down at my feet, which will be the starting position. Then I will start digging for treasure (speeds it up if you make an assist macro to click shovel>target map) moving in a straight line East for 10 or 12 spaces. When I reach that point I throw down another marker. Then I turn south and walk two steps, turn west and start digging up that way. Once I reach the line where the first maker is, I'll turn south again, walk two steps, and start back towards the east again. Keep going until you find it. If you don't find it in that square grid, then have another look at the map and adjust a bit. You won't have to worry about the parts you already marked out.
A quick note on trees and other obstacles, be sure to walk around them and get back in your current line. Not very tough but just a reminder!
After I had done it a few times it would take usually less than 5 minutes to find a location. With some practice it's really very handy but it's probably not for everyone since it actually involves searching.
If you would like me to show you in game, I can later tonight.
Hendric (or Sheldor on Siege)