According to Toshio Okada's (co-founder of GAINAX) 1996 interview with Animerica:
ANIMERICA: Wasn’t NADIA’s story originally by Hayao Miyazaki? Is that the real reason it seems to show so much of his influence?
Okada: Yeah. The original story was going to be called “Around the World in 80 Days by Sea”. That was Mr. Miyazaki’s plan, fifteen years ago. And the Toho people held onto it, and showed it to Yoshiyuki Sadamoto and told him, “You make it.” [...] NADIA was a very hard experience. At first, Sadamoto was supposed to be the director. But after two episodes, he said “Okay, that’s enough for me!” and went back to character design and animation direction, and Anno took over.
So Nadia's original story was by Miyazaki, and it seems very likely that that original idea was part of Castle in the Sky. That is claimed at least by nausicaa.net, but that claim is not sourced (and all google results for "Around the World in 80 Days by Sea" is ultimately sourced from one of these two pages). However, the timing certainly makes it plausible - Around the World in 80 Days by Sea would have been first written ca 1981, while Castle in the Sky was originally released in 1986.