Pode escrever-se com ou sem hífen: «correio elegante» e "correio-elegante".

O Dicionário Michaelis regista a expressão sem hífen: «Correio elegante, Regional (São Paulo): bilhete trocado entre jovens, entregue por um portador, comum em festas populares, especialmente em quermesses, em geral de cunho amoroso.»

O Dicionário Unesp do Português Contemporâneo apresenta a expressão como um composto gráfico, ou seja, com hífen: «correio-elegante [...] bilhete, geralmente de amor, trocado entre jovens em festas folclóricas e quermesses.»

Casos como estes, em que um substantivo e um adjetivo estão associados, nem sempre têm escrita estável e podem, portanto, oferecer variantes ortográficas.