I was interested to knw what new information you found on the Loyalist John Steinhoff of New Jersey and Ontario, and this Melchior Steinhoff you mention.
I know that many people say he was living in Sussex Co., NJ in 1774, but the only record I could find for him was a tax record for that year noting that he owned 10 acres.I scoured records at the New jersey State Library and found a man named John "Stein" or "Stine" who was listed as a Loyalist, but he may or may not be the same, and there were Stine families in NJ as well.
I still have not been able to connect my W.J. Steinhoff (who married Anna Perkins about 1850) to this family, but they came from Ontario Canada, so I think that there must be a connection.
I thought I would also include a note in regard to the origin of the name Steinhoff:
Correspondence with Jürgen-Gernot Steinhoff of Hamburg, Germany in January 2002 offers the following (and his website has some spelling variations of the Steinhoff name): The name Steinhoff means a house or a farmhouse built of stone, and that in former days it was not usual to build a house of stone. The name you will find espacially in the region of Westfalen and Niedersachsen, for exampel around the town Münster and near the region of Braunschweig and as you know around and in Gerbstedt/Mansfeld. There are even Steinhoffs in the Netherlands; they also came from Germany. We find the name Steinhoff for the first time in the year 1036 with Hans im Steynhof in the region of Westfalen. Please also look at the homepage http://home.pi.be/~rebeccas/http://home.pi.be/~rebeccas/
However, I have also received a definition that "steinhoff" could also refer to the paved entryway,patio or foyer to a house or building if there was a something like a walled-in courtyard. According to my great-uncle, Forrest Sheedy (who was fluent in and taught the German language for years, and served as a translator and commander of an anti-panzer division defending the forward command post of General Dean's army, which went through France and germany during WWII), more particularly, "Steinhoff" does not refer to a farm house structure alone, but rather to the complex of a farm house and other buildings surrounded by a common fence or wall: where a house, barn, carriage house, or other out-buildings may have a common wall surrounding or connecting them, built in past times for defense and to keep the most important animals of the household near and protected.