OK, I did try you proposal and correlated subselect.
I have a database ~900000 companies.
First try was to remove randomly selected 1000 companies
Uncorrelated subselect: 65899ms
Correlated subselect: 97467ms
using: 9605ms
my way: 104979ms. (without constraints recreate)
My is the worst because it is oriented on massive delete.
So I thought USING would perform better, so I did try 10000 companies
my way: 190527ms. (without constraints recreate)
using: 694144ms
I was a little shocked, but I did check plans and found out that it did switch from Nested Loop to Hash Join.
I did disable Hash Join, it not show Merge Join. This was also disabled....
and I've got 747253ms.
Then I've tried combinations: Without hash join it was the best result of 402629ms, without merge join it was 1096116ms.
My conclusion: Until optimizer would take into account additional actions needed (like constraints check/cascade deletes/triggers), it can not make good plan.