I've navigated by map and compass in deserts, deep forest, snow covered terrain, jungle and swamps. While it is "difficult" to precisely mark where you are, you can always "guesstimate" if you have a good pace count and kept track of your directions.

The trick, keep the map out, mark where you are as you go along. Oh yeah, if you haven't found what you were looking for, you haven't gone far enough.