E.g. the surname Szulc. I have known only one person with that surname in my life. And that was in primary school. But when I read your question, it was the first name that sprang to my mind.
Because it is actually the winner of my little test. :-)
I started with a list of the most popular Polish surnames, referring to number of persons of a given surname and living in Poland at the beginning of 1990s, registered in PESEL database. The list begins with Nowak (220,217 occurences), followed by Kowalski (131,940) and ends with Lęcznar (270 occurences). That amounts to a total of 20,000 surnames. [The full list, including very rare names, has about 400,000 names]
The topmost foreign sounding name on that list is Szulc (25,556). And there is also Schulz, its cousin. The next on the list are: Serafin, Stelmach, Stec, Misztal, Majcher, Sołtys (sic!), Dec, Koper, Furman, Miller, Lenart, Szwarc, Herman, Roman, Werner, Gut, Szot, Ferenc, Krauze, Wach, Lange, Lorenc, Hoffmann, Knap, Wagner, Bernat, Szubert, Pelc, Frydrych, Schmidt …
If you know the pattern of some typical German names, you can easily create a list of surnames for such pattern by using GREP facility (Regular Expression). For example, the search pattern .+mann$ means: find a line of text that is made of one or more (+) of any character (.) and ends with ($) "mann". When applied to the list like this:
...
6221 Miller
....
4882 Wagner
...
1017 Hermann
...
the "1017 Hermann" will be found.
So here are some samples:
-mann pattern: Hoffmann (5187), Neumann (4259), Lehmann (2050), Hermann (1017), Erdmann (865), Hallmann (825), Ziemann (800), Lademann (685), Stoltmann (598), Reimann (587) ....
-man pattern: Furman (6575), Herman (6249), Roman (5730), Hofman (3167) ...
-ler pattern: Miller (6221), Miler (4216), Winkler (3223), Meller (3140), Keller (2109), Müller (1816), Adler (1371) ...
-ner pattern: Werner (5575), Wagner (4882), Langner (2848), Wegner (2731), Hibner (1308), Bitner (1150), Budner (1028), Lindner (1018) …
Etc., etc.