I'm beginning to research more on the births of my relatives born prior to the First World War. A very general question to anyone else who has done this - Have the majority of birth records from before WWI been lost due to wartime activities, the re-alignment of the borders, etc?
I think most of them are still available in Polish archives (or churches). You may also try to search in other countries like Ukraine, Latvia, or Germany for Polish archives.
I wrote to the priest in the town that my grandfather was born and asked about his birth records. He responded and traced my grandfather and his last name through the church records all the way back to the late 1700's. So I would say that if you know what town they your relatives were born in then the local church would be a great place to start.