One important rule in genealogical research is to look not just at an individual but at the group that the person may be part of, especially when it comes to major events like immigration. People often made significant residential changes in the company of other neighbors, friends, or family. In the case of Henry Stahl this approach ends up being very helpful.
Strassburger & Hinke's Pennsylvania German Pioneers (1934, the Pennsylvania German Society, Norristown, PA, pp.296-297) records a Henrich Stahl as arriving at Philadelphia from Rotterdam on 26 September 1741 aboard the ship St. Mark. Evidence suggesting that this might be him comes from the fact that some fellow passengers on the ship who appear close to him on the passenger list also show up living close to him in later records. Fellow travelers Johannes Flender (just one name away from Henry on the list) and Christian Ohrendorf ended up living close to Henry near Hagerstown, Maryland. Other names seeming to match those on the passenger list - Johann Schneider, Johann Michel, Frederich Klapper, Johann Braun, John Miller - show up on church records in the general vicinity of Hagerstown as well. It is a strong possibility that these others may have been fellow passengers who migrated to the same area as part of overall German migration to that part of the Cumberland Valley.
In particular, Flender (who later changed his name to Flenner), shows up together with Henry often enough to conclude that they knew each other and had a close association. Flender was a member of the Salem Reformed Church in Maryland, the same church where fellow members Henry and "his housewife Anna" were witnesses to events in 1772, 1773, and 1774. In addition, Flender was naturalized on the same day and place as Henry, in 1764 in Maryland and is listed as a member of that church. It seems pretty clear that these two individuals kept in contact over the years. Work by other researchers has shown that. prior to immigrating, Flender was a member of the Krombach Reformed Church, near Siegen, Germany, so the circumstantial evidence suggests that Henry Stahl, Flender, and these others migrated together from the same part of Germany, settled in the same general area, and continued to affiliate with the Reformed Church. This whole pattern of affilitations (i.e. shipmates, church affiliation, residential proximity, naturalization) seems to point to the best possibility for identifying Henry prior to about 1750.
One final note. A 1945 publication on the Stahl family stated that Henry was a Swiss Mennonite, but that claim was a wild fabrication, nothing short of a fantasy. As noted, all evidence points to him being German and a member of the German Reformed Church. The 1764 naturalization record referred to lists all of those being naturalized as German. Many of Henry's neighbors and fellow churchmen were German. The migratory pattern to the Cumberland Valley fits the larger pattern of German settlement of that area. A closer look at the records from the area around Siegen, particularly those of the Krombach Reformed Church, will be carried out soon and will hopefully tie Henry back to his origins in Germany. As information becomes available we will post it here.