Navigation tasks in large virtual environments often call for the use of a virtual map. However, all maps are not alike. Performance on navigation tasks in general has been shown to vary depending on the orientation of the map with respect to the user's frame of reference. This paper reports the results of an experiment investigating orientation issues of virtual maps for use during navigation tasks. Participants were given a virtual map in either a north-up or forward-up configuration. Performance on search tasks was measured in terms of search time and errors. Results indicate that targeted search tasks (tasks requiring only the egocentric reference frame) are best served by a forward-up alignment while primed and naive search tasks (tasks requiring information from the world reference frame) prefer a north-up alignment. Both types of maps are affected by the ability of user to perform mental rotations.