Actually under current EU law, I believe his permanent residency within EU _would_ allow him to obtain work in Poland, which then grants the work permit. The 'permanent residency in a EU country' might however, be a bit shoddy. As a EU citizen however, I can obtain work in Poland and that _will_ make me qualify for the work permit.
Just to add, yes it is a bit catch22, to get the job, you need a work permit, which you will get if you get the job ,)
The extra liability there in case of grey zone situations, can make an employer not offer the job, (due to extra preliminary applications). But, if they are aware of it and arewilling to give you the contract, then the contract qualifies you to a work permit, provided you are either a EU citizen, or (I would have thought , a permanent resident of EU). This might have extra conditions yes, but just saying "you need a work permit" is not the full answer here.
No, there is no catch22, you are complicating things that are clear. As a EU citizen, you can work in Poland without work permit. As a non-EU citizen, Honeymoon55 needs a job offer, and the employer who is offering it has to obtain a work permit for him.
Art. 87 of Ustawa o promocji zatrudnienia i instytucjach rynku pracy regulates which non-EU foreigners are exempt from the obligation to obtain a work permit. Permanent residence in another EU-member state doesn't entitle Honeymoon55 to such exemption.