Ёпрст! Чиновники правы, потому что такого "Zezwolenie na o siedlenie się cudzoziemcowi, który potwierdzi iż jest osobą polskiego pochodzenia" действительно нет. Найдите как это правильно называется на юридическом языке. Пару постов выше helest скинула очень хороший линк на сайт Подляского воеводства. Распечатайте необходимые документы и идите к ним опять. Кричать не надо, какой смысл? Нужно просто спокойно разобраться с недоразумением.
Право Польши обязательно и одинаково везде на всей территории страны.