Permalinks breaking daily

This has been going on for over a month, and there are times the permalinks are guaranteed to break (if we activate/deactivate Ocean Extra, modify a tag name (not the slug). There are also random times the permalinks break (I think corresponding to the host’s backups, but not always.) There are certainly times the permalinks break, when the site appears not to have been touched at all, by any staff.

We have deactivated and reactivated all the plugins, slowly, checking each one. The problem appears independent of plugins, aside from Ocean Extra. We have switched out theme from Ocean and Ocean Extra to Hello Elementor (as our site is with elementor), and we still have permalinks breaking daily.

The site host is adamant that it’s not them. We currently have cache disabled, as the caching system from the host was constant, and required a cache flush each and every time the site was updated. We are going to copy the site to another host, to rule out the hosting as the culprit.

Anything else we can check?