For no apparent reasons, wordpress is returning 404 error on pages that were working fine. Affected pages are product category archive pages. They are a mixture of custom and default pages.

The directory structures that are affected

example/product-category/   

example/product-category/some-sub-category-name

Steps already taken

1. Checked plugins compatibility even though no new plugins were installed prior to that
2. Checked mod_rewrite rules on .htaccess
3. Reset permalinks settings to default and back to custom
4. Cleared cache
5. Renamed the categories
6. Delete and reworked on the affected pages

How can I fix it?