O que "frequentemente" se vai vendo escrito (e dito) é, de facto, de fiar cada vez menos. É o que se passa com os exemplos citados:

a) preia-mar, do lat. plena-mare, mar cheio; o m.q. maré-cheia ou maré-cheias; no Brasil, usa-se, também, preamar (in dicionário Aurélio). "Preiamar" ou, como também se vê por aí, "praia-mar" são barbarismos de linguagem.

b) superestrutura (com o prefixo super só há hífen antes de h, r ou s); como a palavra é estrutura e não a inexistente "strutura", o composto fica superestrutura; mas

c) infra-estrutura. Porque, com o prefixo infra, põe-se hífen sempre que o segundo elemento começa por vogal, h, r ou s.

Cf. Uso do hífen in Respostas Anteriores.