@Tom's answer prompts me to say: yes, the fact Krzemieniec (now Kremenets) is now in the Ukraine adds another layer of difficulty. I'm not sure if my grandmother was able to take the birth certificates with her and lost them (or had them stolen by unscrupulous officials along the way), or if she had to leave them behind. They had an hour to pack and she was able to get a servant to bring another suitcase to the station before they were loaded onto the cattle cars, all in the middle of the night. My grandfather was already in prison, so it was her and four children. The only official documents I have from that period are her 1934 Identity Card, and those issued by the Polish Free Army, and then by British officials during the post-war period.
WWII created so many difficulties for so many families and for their descendants, as did the constant shifting of borders.
From my own research, I've discovered the place names have become a bit garbled as they're passed down through the generations. My uncle mentioned somewhere from his childhood in his dictated memoir, but when I asked on a Polish genealogy group. was told this place didn't exist. Unfortunately, with birth records locked down and not available publicly, this does cause problems for those of us trying to do research based on information that might not be quite accurate. Also, sadly, some records were destroyed during WWII. My dad (born in Krzemieniec in 1935) was never able to get a copy of his birth certificate. A friend of his in Poland tried, and there was no trace of it.
I believe the FamilySearch Wiki keeps its place pages updated. I'm assuming you've been through the resources there for Pomerania, but it's always worth checking back from time to time as more and more material there is digitized, indexed, and made available.
Wish I could offer more help - I know exactly how you feel.