Airbnb faced the cold-start problem for natural language search, needing training data before real user queries were available. Existing methods addressed query generation and relevance labeling separately, introducing potential errors. The proposed CASTLE framework jointly generates synthetic queries and relevance labels from de-identified booking data. It uses contrastive listing pairs, where a booked listing is contrasted with viewed-but-not-booked alternatives. This implicit user preference directly informs the relevance label, fulfilling the query's condition. Query generation is enhanced by template-based, few-shot, and attribute-grounded prompts, along with a variety mechanism. This approach closely matches real user query distributions, unlike previous methods. For cases without booking history, a Virtual Judge is employed. CASTLE significantly improves query distributional alignment and achieves high relevance label accuracy. The framework also helps oversample long-tail intents, providing ongoing value. CASTLE's success lies in complementing booking behavior with LLM generation.