Normalmente abriría Mail.app, haga clic en Mensaje → Codificación → [Una de las codificaciones cirílicas] . Pero desde la actualización no veo la opción de codificación de texto en el menú Mensaje.
¿Cómo cambiar para usar una de las codificaciones cirílicas?
Parece que no eres el único con este problema.
Encontré un artículo de KB en el sitio web de Apple que especifica claramente que Mensaje > Codificación de texto debería estar disponible en la versión de Mavericks del Correo:
Dice "Mavericks" en el título y está vigente a partir del 6 de noviembre de 2013.
He presentado un informe de error para que el equipo de OS X lo sepa.