In Wachstein's Die Inschriften des Alten Judenfriedhofes in Wien › 1540 - 1670, page 117 et seq, he goes into detail about the confusion between Natan Feitel "The Elder", of Frankfurt and R' Nathan Veitel Teomim, A.B.D. of Worms and then Vienna who some sources say is the great-grandson of the former. Wachstein says it is pretty certain that the older Natan Feitel "The Elder", of Frankfurt is not the father of the younger Natan's grandfather Rabbi Moses Ahron Teomim-Fraenkel, because the older Natan Feitel of Frankfurt never went by the name Teomim. Wachstein says that Natan Feitel of Frankfurt could be one of the other great-grandfathers of Natan Feitel of Vienna, but is not certain which one. Wachstein sites a number of earlier sources that he says are clearly confusing the two, and are no doubt the source for some of the wrong information on this part of the tree.
In any case, I disconnected some seemingly wrong attachments and I think we should start from scratch and try to build the tree of the older Natan Feitel to see if it can be connected somehow to the younger one.
P.S. you can access Wachstein's book at http://sammlungen.ub.uni-frankfurt.de/freimann/content/pageview/664361
Pinchas ha-Levi Horowitz, der Schwager Moses Ahron Theomim . . . weiß den jungen Gelehrten, der zur Zeit bereits „mit Rabbinern und Schülern Thora verbreitete", nicht besser zu empfehlen, als die Zeitgenossen daran zu erinnern, daß er der Urenkel des gleichnamigen Nathan Veidel in Frankfurt ist, dessen Lob der Schreiber aus dem Munde R. Schechnas, der größten Autorität der Judenheit in dieser Zeit, anläßlich eines Besuches im Jahre 1556 (ויכפר) hörte. Das den größten Raum einnehmende Lob Nathan Veidels, des Älteren, wird geschickt Nathan Veidel, dem Jüngeren, gutgeschrieben, der ja nicht nur in leiblicher, sondern auch in geistiger Beziehung sein Enkel ist. Fand doch der angeführte R. Schechna selbst eine Beziehung zwischen dem Frankfurter Gelehrten und den Tossafisten.
The Teomim stream is pouring forth a lot of water... I have recently copied the Teomim family tree found in the Levin collection, the handiwork of Rabbi Eliezer Levin. Then I found that the renowned historian Rabbi Zvi Horowitz of Dresden wrote a Teomim history which was published in 1938 and 39 in a little-known rabbinical journal named Unzer Geist (our spirit) published by Rabbi Yisroel Furstman of Zamosz, and edited by Rabbi Hirsch Friedling (a brother-in-law of the noted Talmudist and scholar Rabbi Hirsh Michelsohn of Warsaw who brought this article to the publishers). Sadly, the last issue I have seen is that of Nissan 5699, spring of 1939 with the intended succeeding issue to be September 1939. We all know what happened in Sept. 1939. Was the next issue already printed prior to the German invasion? Is there still a copy somewhere? I do not know, but I have copies of 4 instalments. Then I found the transcription of the grave of Avrohom Peretz Feitel Teomim Munk of Vienna, who became rabbi in Hotzenplotz. I found it this morning in my copies of the Levin archive, but it was already discussed by my grandfather in an article he published in 1911 about Vienna exiles (of 1670) coming to Hotzenplotz.
I also searched for Natan Veidel (Teomim) (Munk) the elder in Frankfurt by looking in Ele Toldot, and was also surprised not to find a mention. However, I have a number of possible answers. (1) Let us go to the source which links him to Frankfurt. Pinchas Horowitz of Krakow, who was born in Prague and traveled to Poland to study with the world's greatest authority of the time Rabbi Schachne of Lublin. (All those mentioned deserve detailed honorifics, and are all scholarly rabbis, so I will be concise and omit titles.) Pinchas' sister, Rebecca (my ancestress) married the son of Nathan Veidel the elder, and Pinchas later published the writings of his nephew Nathan Veidel Munk-Teomim of Vienna. Pinchas published two homiletic works of this nephew in Krakow 1589 and 1613, where Pinchas and his son owned or sponsored a large printing press. They also sponsored the publishing of other works by scholars in the family, such as Shulchan Aruch with glosses of Rabbi Moshe Isserles (whose sister was Pinchas' wife and was thus his brother-in-law). On the title page of nathan Veidel the younger's works Drushim lechol Cheftzeihem and Derush leparshas Vayigash http://www.hebrewbooks.org/45769 is found this anecdote of Rabbi Shachne saying that Natan Veidel of Frankfurt is the wisest of the rabbis in Frankfurt and is of the family of the great authors of Tosfos.
So this source does not prove he lived in Frankfurt but only that he was one of teh scholars of the yeshiva there. This would be one possibility.
2. Many families in that period used several family names, and although some scholars have written about this I do not think we fully understand the multiple uses and when one was used and when another. For instance, the Teomim family are also called Munk and also called Laemlin or Laemle or Lemmlin, the Ele Toldot itself struggles with these multiple nomenclatures.
According to Ettlinger Natan Wiesbaden son of Mordechai in the house Lamm died 31 Mar 1656. I don't see anything on his page that would make him the same as Natan Veidel.
And what does that source say that says Natan died 1569? His wife iRivka s listed as born 1550. I wonder if there is a clue on the Luria side.