Virtual influencers (VIs) are increasingly integrated into brand communication strategies, offering novel opportunities for audience engagement, message control, and digital differentiation. This study examines brand-virtual influencer collaborations through a multiple-case study approach, analyzing five diverse cases: Lil Miquela, Imma, Noonoouri, Lu do Magalu, and Knox Frost. The analysis focuses on brand motivations for engaging with virtual influencers, strategic design and implementation choices in VI collaborations, and their effects on consumer trust, brand perception, and engagement. Findings indicate that brands are primarily motivated by novelty, differentiation, and the ability to achieve risk-controllable visibility, while effective collaboration strategies depend on aligning virtual influencer characteristics such as form realism, ownership structure, and endorsement format with product category and communication objectives. Cross-case synthesis reveals what we conceptualize as the Credibility-Engagement Paradox: an analytical framework whereby novelty, originality, and visual distinctiveness enhance engagement and opinion leadership, while simultaneously constraining perceived credibility and trust relative to human influencers. This study advances influencer marketing theory by conceptualizing the Credibility-Engagement Paradox as an analytical framework derived from cross-case evidence, demonstrating how novelty-driven engagement and credibility formation operate as partially independent mechanisms shaped by anthropomorphism, ownership structure, and contextual accountability, while also offering actionable guidance for brands deploying virtual influencers in digital marketing ecosystems.