The whole thing seems to be getting more troublesome all the time.

I only have worked for universities and the three times that I moved 'out of province' the universities cooperated with each other, though I did need to travel in May to the new university's city to get my picture taken for the new RP and leave my passport. I did once need to convince the university to generate an 'early' termination letter without actually canceling the RP.

The situation does change to some extent every year and I'm not aware how private schools or high schools negotiate the process.

You can negotiate the 30 day extension of your existing RP yourself, but that doesn't solve the problem. Your new employer seems less than motivated.