Instead of removing holdings would it be possible to add button to 4th and later holding slots (if province has already build castle, city and bishopric) that would change the holding type. It would be cheaper than building new holding and convert some of existing improvements. To make it less exploitable make it dependable on ruler focus. Businesses or rulership focus to change holdings into city, war focus to turn it into castle, theology(?) focus for bishoprics.
It would not happen instantly. Selecting holding for reconstruction would lead to gold draining events (secure land for resettled people, compensation to local nobility etc.), having steward oversee construction would speed up the process.