En el CORDE aparece palmo de narices con su sentido figurado actual (o similar) en 1705 y luego en 1769, ambos con la aclaración "como dicen", que sugiere que la expresión todavía requería alguna aclaración. En la primera de estas citas da la impresión de que el significado es de "verse impedido" más que de "ser víctima de un chasco":
…abrió la puerta por cumplimiento, pero no quiso dejar entrar ninguno
porque estaba dentro. Con que se volvieron a salir, con un palmo de
narices como dicen…
Dado que la expresión en cuestión parece tener una larga historia, fui a buscar a ver si encontraba algo similar en el portugués. Me encontré con que
Está claro que hay una relación entre las expresiones de ambas lenguas.
¡Pero hay más! La misma expresión exacta aparece también en italiano: con un palmo di naso, que según el Wikcionario significa deluso e allibito, o sea, "frustrado y atónito, desilusionado y desconcertado", etc. De manera que ya van tres lenguas romances con una expresión equivalente.
A esta altura tampoco me sorprendió encontrar que en francés faire un long nez ("hacer una nariz larga") significa "estar decepcionado o contrariado".
El gesto de burla con las manos referenciado en la Wikipedia en español como posible origen de la expresión "palmo de narices" se llama en francés pied de nez (pied = pie, unidad de medida). Faire un pied de nez significa "burlar" y no parece que tenga relación directa con faire un nez long, pero no creo extraño imaginar que una haya influido en la otra.
No tengo una respuesta clara para concluir, pero imagino que el par de expresiones francesas, asociadas, pudieron haber llevado a un doblete como el que hoy existe en español:
dejar a alguien \
|- con un palmo de narices
quedarse /
