It will take some process to configure / set up your phone again, if you didn’t create usable backups without the “bug” included in them (else they’re unusable).
A factory reset could help to solve bugs and hassle which an update might bring (and some people do a factory reset after bigger updates to ensure a clean configuration to start from), but it is no guarantee. Depending on how much work you’ll have to set up your system again, I would in your situation decide for or against it.
But one aspect is clear: just from resetting the application related data this bug isn’t removed, neither did the recent updates fix it (most probably due to the faulty / misconfigured part not getting overwritten, as no newer version was included).
And without internet access for the applications your phone is quite limited in its functionality…
In your situation I would save / backup whatever is important, do a factory reset, if this doesn’t work, re-flash the /e/ OS via CLI in full process. But this takes its time, needs understanding of the procedure (and the tools ready) and bears risks. For me it still would be better than a phone with such a grave bug.
Edit: Did you maybe set this option? Seems as “Block connections without VPN” option creates flaws for other users which remind me of your symptoms.