Unfortunately this is not at all uncommon. Legacy products get EOLed for lots of different reasons, some for technology (ie, fab lines going EOL, or in this case due to a high Pb packaging process in an era that is moving to Pb-free technologies). Or many times just demand for older products; not enough orders to justify running the older fab / assembly processes.
And not having the vendor supply a direct drop in, fully compatible replacement part, is not uncommon either. In fact it is usually what happens for more complex technology devices that are single sourced.
So you have basically two options ... if you must/want to continue producing that product as is, figure out how many parts you will need over the remaining lifetime demand for your product, and then order / buy those parts, and hold them in inventory. Can be an expensive proposition.
Or possibly just roll the dice, hoping that vendors that deal in old, obsolete parts may be able to source parts for you in future years, possibly at an inflated per-device cost.
Or redesign your product to move to a new CPLD/FPGA technology that has an EOL timeframe that is (way) out in the future, so you can buy parts from stock as you need them from distributors.