No caso do nome próprio, não há de facto ortografia clara.

Há quem escreva com hífen, e há registos sem este sinal. O mesmo acontece, com Barba-Roxa/Barba Roxa, ou, ainda, Barba-Ruiva/Barba Ruiva¹.

Quanto ao nome comum composto, não há dúvida, pois escreve-se com hífen: barba-azul².

Por outras palavras, Barba-Azul é forma correta, atendendo até à forma do nome comum³. No entanto, também se aceita Barba Azul.

¹ No Vocabulário da Língua Portuguesa (1966), de Rebelo Gonçalves, escreve-se Barba Roxa, sem hífen, mas no Vocabulário Onomástico da Língua Portuguesa (1999), da Academia Brasileira de Letras, hifeniza-se Barba-Roxa e Barba-Ruiva; infere-se, portanto, que Rebelo Gonçalves teria escrito Barba Ruiva sem hífen, se tive registado este nome próprio. Observe-se que os vocabulários ortográficos atualizados não contêm a grafia de nomes próprios, e, sendo assim, convém consultar fontes anteriores à aplicação do Acordo Ortográfico de 1990.

² No vocabulário de Rebelo Gonçalves (ver nota 1), regista-se barba-azul como substantivo comum.

³ No dicionário da Academia das Ciências de Lisboa, apresenta-se a forma hifenizada, Barba-Azul, quando se refere a origem do nome comum barba-azul.