Under a high-density traffic environment in a vehicular ad hoc network (VANET), many safety messages will not be verified in time and then get dropped. To touch such an issue appropriately, we aim at improving the efficiency of message verification and the number of verified safety messages. In our proposed scheme, messages are properly classified and prioritized first so that more important basic safety messages can be verified earlier. To improve batch verification, a dynamic batch verification scheme with an adjustable batch size is designed accordingly. The batch size is halved when failures of batch verification occur consecutively over a certain threshold to improve the efficiency of batch verification. On the contrary, the batch size is doubled when successes of batch verification occur consecutively over a certain threshold to increase the messages in a batch to be verified. For a failure of batch verification, a divide-and-conquer approach is utilized to find the illegitimate message(s). Via analysis, the superiority of our design over some closely related schemes in terms of verification delay and number of verified basic safety messages etc. is successfully demonstrated. By simulation, performance of our design and some closely related schemes is further investigated in realistic scenarios.