Os dicionários (o Houaiss e o da Academia das Ciências de Lisboa) que consultei indicam que se trata de uma expressão com sentido figurativo:

«procurar uma coisa muito difícil de achar».

Não pude encontrar obras que explicassem pormenorizadamente a origem desta expressão, mas considero que a sua origem rural é muito provável, dada a inclusão da palavra palheiro, ligada ao mundo agrícola.