As I tried to follow this thread, I found the place names a bit confusing. Maybe you have it sorted, Paul O? Political terms and geographic terms are mingled, as are archaic and newer place names and Danish and American names.
Paul O. great-grandfather "died in 1928 and is buried in Kongsted, Sjælland, Denmark."
Sjælland is an island. (Americans sometimes call Sjælland, Zeeland.)
Paul LS found the death record at Kongsted, Fakse, Præstø.Kongsted, Fakse, Præstø is on the island of Sjælland.
The death record led Paul to the family in Rønnebæk, Hammer, Præstø. (Lissa found the exact same family, researching it from another direction.) The family lived at Steenstrup, Rønnebæk, Hammer, Præstø.
Paul O's father thought the place name Steenstrup was applied to this family (as place names were sometimes applied to families). That surprises me, as Peter Sorensen's family was relatively new to Steenstrup. (Usually that kind of place name-surname gets stuck onto a family in an earlier era.)
Paul O's great-grandfather was "born about 1841 in Øster Ulslev, Storstrom, Denmark." Storstrøm is an archaic Danish amt. This link describes the amts that were once part of Storstrøm. LINK: http://en.wikipedia.org/wiki/Storstr%C3%B8m_Countyhttp://en.wikipedia.org/wiki/Storstr%C3%B8m_County
The place "Steenstrup, Rønnebæk, Hammer, Præstø" would have been within Storstrøm. There's no contradiction with the American story.
Paul and Lissa could not connect "Øster Ulslev."
On another topic, could this be your Peter Sorensen?
A DANISH EMIGRATION RECORD
Navn: Sørensen, Peter Stilling: Tømrer[carpenter] Alder: 28 [born about 1840] Bestemmelsessted: Racine Kontrakt nr.: 32800 Forevisningsdato:7/21/1868 Sidste oph.sogn: ? Sidste oph. amt: Sorø Sidste oph. sted: Stenstrup Sogn, Sorø Amt ******* Bestemmelses land: USA Bestemmelses by: Racine Bestemmelses stat: Wisconsin Skibsnavn: Indirekte [ship's name: none, going by indirect route] Bemærkninger: Opr. Idnr: I680005313 IDkode: I1868P0077
*******As far as I know, there is no Stenstrup SOGN in Sorø amt, and this must be a mistake (should be Praesto amt).