I deleted my old Apple ID but forgot to log out from iCloud. I now can't reset my phone without turning off Find my iPhone because you need to sign in to iCloud to turn it off. I asked Apple Support to restore the account, but they say they can't.
This article looks like it may be your answer. It details how to deactivate your old AppleID in particular. You could also, if I understand your problem, put your AppleID back on the iPhone, turn off Find my phone, then again delete the appleID. Or check this link for ways to do it without having your iPhone set up again.