O curinga (o * ) deve ser a parte mais à esquerda do domínio. Então você não pode fazer stage.*.example.com .
Se você precisar usar DNS curinga para isso, sugiro usar *.stage.example.com . Isso pode exigir algumas pequenas alterações nos processos de implantação, mas não deve ser significativo.