Finding my grandmothers birth place in Poland was a fairly easy one - we had the name, but since history was kept quite, we needed confirmation.
So i googled quite a bit, and actually found a same surname person living in her town of Birth, (SE Poland), i actually found this person on the Polish google - i wrote to him, and it was a 2nd cousin and of course my grandmothers place of living prior to WW2.
My grandfathers place of birth was different - the spelling we had was not correct, and actaully, we had different spellings from different documents - all of which could of been another town altogether. Border changes did not help the situation at all, and at one stage i was searching in Poland, but as it turned out, its the Ukraine. It took about 1 year and a bit to really get confirmation and this was done through the article i had put in their local paper.