WordFence could not register error

I have tried to troubleshoot and fix this issue for hours on one of our websites. We are getting the message:

Wordfence could not register with the Wordfence scanning servers when it activated. You can try to fix this by deactivating Wordfence and then activating it again, so Wordfence will retry registering for you. If you keep seeing this error, it usually means your WordPress server can’t connect to our scanning servers, or your wfConfig database table cannot be created to save the key. You can try asking your host to allow your server to connect to noc1.wordfence.com or check the wfConfig database table and database privileges.

We have deactivated and activated the plugin multiple times, including after tell it to delete all the databases and info on deactivation. We have checked with our host who says nothing is being blocked that would be causing this.

Under Diagnostics > Tools is says:

Wordfence Config Ability to save Wordfence settings to the database.

And, both Checking basic config reading/writing and Checking serialized config reading/writing have “X’s” next to them.

I’m not sure where to go from here. So much time spent trying to troubleshoot this already, when it was working previously just fine.