i changed my apple id but now my phone is my old id and i have since deleted it and now cannot access my apple id on my phone

From the article below.

Make sure that you sign out of all your devices to avoid issues with apps that use your Apple ID account or iCloud. After your account is deleted, you can't sign out of iCloud or turn off Find My iPhone Activation Lock on your devices. If you forget to sign out, you might not be able to use your device when your account is deleted.

How to delete your Apple ID account.   *  

If you logged out of iCloud and all, where do you still need to sign out?

As I posted above.

Make sure that you sign out of all your devices to avoid issues with apps that use your Apple ID account or iCloud. After your account is deleted, you can't sign out of iCloud or turn off Find My iPhone Activation Lock on your devices. If you forget to sign out, you might not be able to use your device when your account is deleted.

I logged out of my Icloud and all but I cant sign out of my deleted apple ID since it requires a password but as my account is deleted it says "person cant be found" and now i cant sign out anymore and I'm stuck with it.

If you did not sign out before you deleted your apple ID, is the recourse to reset everything and wipe the phone clean? Start over?

Unfortunately, that won't help.

I am not trying to recover my older ID. I know its gone.

But cant I use another apple ID to that is valid and just start over.

I didn't have any apps purchased as this was a work device.