Pseudonyms are pseudonymous certificates, which are regarded as a silver bullet to meet the security and privacy requirements of vehicular communications. Most works so far assume that pseudonyms are readily available when they are needed. In this paper, we identify and compare two strategies to refill pseudonyms. We then propose the pseudonym-on-demand scheme, which is an implementation of one of the strategies. We show that our approach supports the functionalities of pseudonyms in terms of secure and privacy-preserved vehicular communications. Furthermore, our proposed scheme serves as a platform, into which many features to enhance security and privacy can be integrated.