In Vehicular Communication (VC) systems, neighboring vehicles exchange authenticated transportation safety messages, informing about own mobility and the environment. Verifying all received messages in a dense neighborhood introduces significant cryptographic computation overhead for resource-constrained vehicular On-Board Units (OBUs). Attackers can exploit this to launch Denial of Service (DoS) attacks to clog OBUs by broadcasting bogus messages at a high rate. This attack is particularly effective due to an inherent asymmetry and amplification factor: each safety message is to be validated by all receiving neighboring vehicles. This imbalance can lead to significant delays in sifting benign messages amidst a deluge of bogus messages. Even worse, failure to promptly verify a significant amount of benign messages can paralyze Vehicle-to-Vehicle (V2V) enabled applications. We address this challenge, proposing a mechanism that thwarts such attacks: puzzle-based pre-validation that prioritizes verification of potentially valid messages with yet unknown (i.e., unverified) Pseudonymous Certificates (PCs). Verification of such PCs (and their corresponding messages) can bootstrap the efficient pre-validation of follow-up messages authenticated by the same PCs. We show experimental results confirming our scheme can effectively mitigate unsophisticated clogging DoS attacks that do not attempt to solve puzzles. We further show our scheme also significantly raises the bar for sophisticated adversaries: it can be configured to force attackers to solve puzzles for their bogus messages actively - something possible only by investing in significantly higher (hundreds of times more) computational power than that of the targeted benign vehicles. Last but not least, our scheme can be adaptive while remaining compatible to standardized V2V security.