Effective and robust operations, as well as security and privacy are critical for the deployment of vehicular ad hoc networks (VANETs). Efficient and easy- to-manage security and privacy-enhancing mechanisms are essential for the wide-spread adoption of the VANET technology. In this paper, we are concerned with this problem; and in particular, how to achieve efficient and robust pseudonym-based authentication. We design mechanisms that reduce the security overhead for safety beaconing, and retain robustness for transportation safety, even in adverse network settings. Moreover, we show how to enhance the availability and usability of privacy-enhancing VANET mechanisms: Our proposal enables vehicle on-board units to generate their own pseudonyms, without affecting the system security.