A formulação que refere é uma formulação possível em português, mas que é vulgarmente utilizada nas datas escritas por extenso na transcrição de actas ou em certos documentos legais, como as escrituras; nestes casos, a data é, aliás, geralmente escrita por extenso na sua totalidade (e. g.: «aos vinte e três dias de Abril de dois mil e dez»).

Nas restantes situações, entre as quais a correspondência, mesmo formal, a fórmula consagrada consiste na indicação do local de emissão, separado da data por uma vírgula, escrevendo-se primeiro o dia, depois o mês e, por fim, o ano, sendo estes elementos ligados pela preposição de (por exemplo: «Lisboa, 23 de Abril de 2010»). Como se pode ver, nestes casos, o dia e o ano são notados através de dígitos, sendo apenas o mês escrito por extenso; para além disso, ao contrário do que acontece numa escrita mais abreviada, não se coloca o zero antes do dígito que indica os dias (veja-se «Lisboa, 3 de Abril de 2010»).

Quanto às datas escritas apenas com dígitos, a norma internacional (ISO 8601) e a própria norma portuguesa (NP EN 28601) preceituam que a ordem é inversa, ou seja, ano, mês e dia (2010-04-23), embora o peso do costume mantenha corrente a ordem dia, mês e ano (23-04-2010).

Para concluir, penso que a questão que apresenta é sobretudo de ordem estilística e prende-se com o efeito que pretende criar junto de quem lê a sua carta. Penso, contudo, que, apesar de pretender um efeito clássico e distinto, a formatação «Lisboa, 23 de Abril de 2010» será a mais adequada para correspondência. Ressalve-se ainda que a utilização da forma abreviada da data, particularmente vulgarizada na correspondência comercial, não é necessariamente sinónimo de informalidade. Em suma, tudo depende da adequação ao contexto em que se encontra.

Espero ter respondido de forma esclarecedora à sua questão!