404 After Deactivating Plugin Despite Permalink Regeneration

Some time ago, after updating WPML, some categories of my site, randomly, gave 404 error without any reason. I was advised to give up the category strip and so I decided to disable No Category Base.
Since then I can not solve this problem in any way: if I turn off the plugin all categories and subcategories (but obviously not pages and posts) return me code 404. I’ve tried dozens of times to regenerate the permalinks but nothing changes. Also, it seems incredible, the url without category is still active and the categories without /category/ are loaded correctly, which makes no sense since the menu structure has all the url that require /category/ instead.

Example: https://www.mysite.it/cat-name
with No Category Base enabled it seems to work correctly. But randomly it could give 404 error that I fix sometimes deactivating and reactivating the plugin, other times I’m forced to load a backup (I’m not sure, but it seems that the categories involved have no post).

If I disable the plugin, all menus point to https://www.mysite/category/cat-name and if I navigate to that url I always get 404. In the previous case only some categories give 404 in this case instead all categories give 404.

As I said I tried to regenerate permalink dozens of times, I disabled functions.php, then changed the theme with Twentyfifteen, disabled all plugins, changed servers, but nothing to do, there is no solution to the problem.

I would like to know if you have any advice to give me and if someone has reported similar problems in deactivating this plugin.
Thank you!