Looks good. These polish details are usually overlooked.
I suggest something of a combination. In your Photoshop/GIMP, you can combine layers. One for the overhead image of the map, one for building outlines and out-of-bounds, one for stains and paper to resemble a real map, etc.
Check out the maps used in Company of Heroes. They use overhead maps and stencil over the top of them in Photoshop, using several layers including building outlines, water, roads, and foliage. They blend and merge the layers together in a way which makes the markers on the map easy to see, but also let you know exactly where you are.