Looking for any leads on origin of my grandfather, Theodore J. PUCHALSKI or PUHALSKI. (On my father's birth cert in 1905, the name was spelled Puhalski, but on my aunt's birth certificate a year later, filled out by a German doctor, the name was spelled Puchalski.)

Theodore was b Germany abt 1876, but spoke Polish, so I think he was really born in the region of what used to be Prussia. He emigrated to NYC abt 1884, and lived in Brooklyn, Kings Co, NYC for most of his adult life. He m Sophie LASKOWSKI, dau of Anton LASKOWSKI and Mary Jankowsky, from "Posen," abt 1904. They had two children: Valentine Joseph and Anna Mae.

I have found absolutely no way to get past this brick wall, and would appreciate any help. I cannot find him in marriage records, immigration records, passenger lists, etc. Not sure what else to do...