iPhone 4 asks me to log into an Apple address that Apple say doesn't exist
Start by recovering the password to example22@example.com at https://iforgot.apple.com (and use the guidance provided there in case you don't know the answers to the security questions). Then proceed with decoupling your phone from the old ID.

If you are unable to recover the password to example22@example.com, Apple can remove the old AppleID from your phone. You need to show proof of purchase for this though.