Na construção de caminhos de caminhos de ferro no Brasil, marcavam-se com estacas o traçado da linha. A estaca zero era a primeira estaca, que marcava o início da linha. Daí que voltar à estaca zero viesse a significar recomeçar uma coisa desde o princípio.
Encontram-se no Google Books muitas referências a estaca zero a propósito do planeamento de caminhos de ferro no Brasil a partir do último quartel do século XIX (negrito meu em todas as citações):
Dei começo á variante, partindo justamente da estaca zero, implantada pelos agentes da companhia para o respectivo ponto de partida
Estrada de Ferro D. Pedro I.: Parecer da Comissão Fiscal, 1885.
A extensão total dos trilhos assentados entre a estaca zero e a ultima estaca, além do gyrador em Araraquara, inclusive todos os desvios nas estações, monta em 51,093.73 metros correntes.
Revista de Engenharia, Vol. 7, 1885.
Imagino que também se usassem estacas para estradas, linhas de telégrafo e coisas assim. Na verdade, o Aulete, como apontou o Stafusa, e vários outros dicionários definem estaca zero como ‘a primeira estaca num levantamento topográfico’. Mas é sobretudo a propósito de caminhos de ferro que encontrei a expressão no sentido literal. Esta Collecção das leis do Estado de Minas Geraes de 1895 sugere que as estacas na marcação de caminhos de ferro eram cravadas de 20 em 20 metros.
A mais antiga referência que encontrei a voltar à estaca zero no sentido figurado é de 1946, no Brasil. Pelo que o autor diz, a popularização da expressão devia ser recente:
O inquérito teve início mas, como todos os inquéritos no Brasil, parou. Usando uma expressão muito em voga, voltou à estaca zero. Não sei o que isto quer dizer, mas penso que significa parar, porque encontrou obstáculos sérios que não convinha remover.
Mineração Metalurgia, vol. 1(65-66), 1936.
A partir desta data, o uso figurado de estaca zero é muito comum no Brasil. Fora do Brasil, o exemplo mais antigo que encontrei é de 1974 em Angola. Não tem o voltar, mas a noção de começar do princípio, do nada, está lá:
Estaca-Zero, era a palavra pronunciada não há muito tempo pelas gentes que visitavam o Cuando Cubango [...] Queriam eles dizer que nada estava feito, além da fundação de Menongue, três ou quatro vilas e meia dúzia de postos administrativos.
O Turismo, Centro de Informação e Turismo de Angola, 1974, mais outro excerto para completar.
A mais antiga que encontrei em Portugal é de 1988:
Não acreditas então que os comunistas vão deixar de ter lugar no mundo moderno?
Nem por sombras. Voltámos à estaca zero, mas já não é a primeira vez.
(Política Operária, 16-32, 1988.)