Applying Varying Pseudonym (VP) to design of Radio Frequency Identification (RFID) authentication protocol outperforms the other existing approaches in several respects. However, this approach is prone to the well-known denial-ofservice (DOS) attack. In this paper, we examine the de-synchronization problems of VP-based RFID authentication protocols, and propose effective solutions to eliminate such weaknesses. We shall show that the proposed solutions indeed improve the security for these protocols, and moreover, these solutions require 0(1) computational cost for identitying a tag and 0(1) key space on the tag. These excellent performances make them very attractive to many RFID applications.