I have set up an account recovery key. When i type it in the verification I get an error message saying VERIFICATION FAILED. YOUR RECOVERY KEY IS INCORRECT.

The most likely cause appears to be that one or more of the devices associated with your AppleID (phones, watches, computers, appleTVs, etc.) are not running the most current iOS version.

You can confirm this as the root cause of the issue by trying to set up Advanced Data Protection on an Apple computer associated with your account. Instead of the usual "verification failed" message, you should get a list of devices that need to be updated before ADP can be enabled.

Hope this helps!