Não consegui descobrir quando é que de nada começou a ser usado como resposta a um agradecimento. Mas no século XVIII, possivelmente até mesmo no limiar do século XX, a frase “Vossa Mercê não está obrigada de nada” não suscitaria qualquer estranheza e seria entendida como “Vossa Mercê não está obrigada por nada” ou “Vossa Mercê não tem qualquer obrigação.” Portanto, fosse qual fosse a origem de de nada, a sua adoção seria facilitada por obrigado de nada ser no passado, ao contrário do que se passa atualmente, imediatamente compreensível.
Esta questão existe também no SE Spanish Language sem uma explicação cabal da preposição de. Também para o falante moderno do castelhano a preposição por seria mais natural. Um comentário à pergunta diz que o de nada castelhano vem do francês de rien, que uma resposta à questão equivalente no SE French Language diz ser um redução de ne me remerciez de rien.
Vontando ao português, obrigado usou-se até pelo menos ao século XVIII com a preposição de. Obrigado de era entendido como obrigado por, forçado por. É possível que obrigado de fosse assim compreendido ainda no limiar do século XX:
Logo publicamente, obrigado do poder divino, confessou que era o demónio do inferno, o qual havia catorze anos que andava naquele castelo, (Francisco Saraiva de Sousa, Báculo pastoral de flores, 1624)
Nos 14 annos de Gorgoris succedeo o incendio de troya, e hum dos que prezunciarão esta fatalidade, foy Olisses Rey de Ithaca. Este na retirada, que fazia com os seus, obrigado de huma furiosa tormenta, entrou pelo Rio Tejo [...] (Frei Manoel da Mealhada, Promptuario historico II, 1760.)
Antônio José não só não seguiu nessa parte os modelos recentes, mas até carregou a mão sobre o que imitou de Plauto. A alegria do seu Anfitrião e da sua Alcmena é tão franca, tamanho é o alvoroço dos dous esposos, que realmente chega a ofender as leis da verossimilhança, ainda tratando-se de um caso divino. Neste ponto Antônio José foi antes inadvertido do que obrigado do gosto público. (Machado de Assis, Críticas, 1906.)
Esta ocorrência de obrigado de foi a única posterior ao século XVIII que encontrei com o sentido de obrigado por. Daí ter qualificado como apenas possível o seu uso ou compreensão no limiar do século XX. Possivelmente seria na altura um arcaísmo. Machado de Assis nasceu em 1839. Nos exemplos anteriores, é uma força exterior que obriga. Nos seguintes, o que obriga é um sentimento de gratidão. Em português moderno, poderíamos substituir o obrigado de por grato por::
O mancebo, alheio destes pensamentos, porém obrigado das mostras que lhe revelavam aquela afeição, determinou de lhe não ser ingrato (Francisco Rodrigues Lobo, Côrte na Aldeia e Noites de Inverno, 1607.)
Morto o Egypcio, [Antioco] renovou a guerra, e tomou Celesyria, Phenicia, e Judea. Diz Josepho, que obrigado do grande festejo com que os Judeos o receberaõ, eximira os Sacerdotes dos tributos, e lhe facultou o viverem conforme sa suas leys. (Frei Manoel da Mealhada, Promptuario historico I, 1760.)
Escreve Luciano, que indo Antioco contra os Galatas, lhe appareceo em sonhos a figura de Alexandre, a qual lhe deu hum sinal de tres triangulos por sinal e penhor do vencimento; e foy assim, que quando em meyo da batalha Antioco levantou aquella figura contra os Galatas, alcançou logo vitoria; de que obrigado Antioco mandou lavrar moeda, que continha de huma parte a figura revelada de Alexandre com os tres triangulos, e da outra estas letras Gregas ??????, que se interpretárão, saude; e methaforico, vitoria. (Francisco Manuel de Mello, Tratado da sciencia cabala, ou Noticia da arte cabalística, 1724.)
A passagem seguinte é a mais antiga em que eu encontrei obrigado usado praticamente como atualmente, mas em que o significado original é ainda muito explícito:
Sabereis que é já chegado o B~reve [?] muito à minha satisfaçao e assim já nao há necessidade de fazerdes viagem tao trabalhosa. Eu vos fico tao obrigado, como se efectivamente a empreendesseis e me mostrarei sempre à vossa boa vontade agradecido. (Manoel Consciência, Academia universal, 1732)
Como nesta época se dizia obrigado disto e obrigado daquilo, seria perfeitamente possível responder ao senhor, “não tendes que ficar obrigado de nada.” Com o desaparecimento da construção obrigado de, não admira que o de nada soe um nadinha misterioso ao falante moderno do português.
As mais antigas respostas que encontrei a um agradecimento foi no final do século XIX sob a forma não há de quê. Isto corresponde exatamente ao francês il n'y a pas de quoi. Em português poderiam ser entendidas como não tem de que agradecer ou não tem de que ficar obrigado.
ÂNGELO (Erguendo-se e entregando o cheque) - Obrigado pela comissão do marido. ESPOSENDE - Não há de quê. (Artur Azevedo, O Dote, 1888.)
LUÍSA - Obrigada... pela parte que me toca! DR. PEREIRA - Não há de quê! (França Júnior, As Doutoras, 1889)
