Cognitive radio (CR) vehicular networks are poised to opportunistically use the licensed spectrum for high-bandwidth intervehicular messaging, driver-assist functions, and passenger entertainment services. Recent rulings that mandate the use of spectrum databases have introduced additional challenges in this highly mobile environment, where the CR-enabled vehicles must update their spectrum data frequently and complete the data transfers with roadside base stations (BSs) in very short interaction times. This paper aims to answer two fundamental questions: 1) when to undertake local spectrum sensing, as opposed to accessing spectrum database information at a finite cost overhead; and 2) how to ensure correct packet receptions among the multiple BSs and CR vehicles using fewer slots than the messages that need to be transmitted. The contributions of this paper are twofold: First, we introduce a method of qualifying the correctness of spectrum sensing results using out-of-band 2G spectrum data using experimental results. Second, to the best of our knowledge, this is the first work on applying the concept of interference alignment (IA) in a practical network setting, leading to dramatic reduction in message transmission times. Our approach demonstrates significant reductions in the overhead of direct database queries and improvement in the accuracy of spectrum sensing for mobile vehicles.