I use http://www.geonames.org/http://www.geonames.org/ (and use fuzzy search, under "Advanced" to help you correct for any possible misspellings. ) to search for places, because GeoNames also includes rivers, mountains, parts of towns, you name it.It doesn't have "everything," but it is the most robust search tool I know of for places.
Next, if you look in the 1880 census for your ancestor, you'll notice a place of birth that reads "Reus".I had a similar situation where a surname was written once as "Sueser" and a family member pronounced it as "Sieser," but the German records read "Süsser."I mean to tell you not to count on vowels in German-English translations.There is a Rees in Prussia... food for thought.Also as you can see, the number of s's are different... maybe you are looking for Reuss?The final "s" in the 1880 census looks to be an "esszet" or "ß".
I would try to find your ancestor in emigration books (Hamburg, Württemberg, Baden, etc.) to see if there is a clearer record.
He seems to clearly state that the kingdom was Prussia, so the only way I would believe otherwise is if it were an area under dispute by the two Kingdoms, or you have compelling evidence otherwise.For example, see the purple areas here: http://upload.wikimedia.org/wikipedia/commons/b/b6/KgrWuerttemberg.pnghttp://upload.wikimedia.org/wikipedia/commons/b/b6/KgrWuerttemberg.png
Try searching with R*s or R??s as a place name instead of using "Duke Reis".You may find more.
One area that is the most compelling is Thuringia and Saxony, specifically Plauen.Plauen is on the border between the two modern states.Geonames shows a "Reusa" just outside of Plauen, and a "Reust" just outside of Gera.These two towns used to be part of the Reuß State, which would have been in decline when your ancestor was alive, but probably the candidate we are looking for. These two towns are about 50km or 30mi away from each other.But in all likelihood, you are going to be looking for another town in this area.http://en.wikipedia.org/wiki/Reuss_(statehttp://en.wikipedia.org/wiki/Reuss_(state)
As this area was ruled by a prince, perhaps this explains the "duke" part of your search.