Inter-vehicle communication is regarded as one of the major applications of mobile ad hoc networks (MANETs). In these so called vehicular ad hoc networks (VANETs) security and privacy are crucial factors for successful deployment. In a scenario, where each vehicle would have a unique identifier, eavesdroppers could easily accumulate location profiles. As a solution approach, several authors suggest using changeable pseudonyms as temporary vehicle identifiers. If a vehicle changes its pseudonym from time to time, long-term tracking can be avoided. However, as we show in this paper, changing identifiers has detrimental effects on routing efficiency and increases packet loss. So, designers of VANET systems need to aim for a balance between privacy protection on the one and performance on the other hand. The results of this paper provide advise on how to achieve this balance.