Zaki, could you take the following outline and gather the info I'm requesting and update your question to include it so I can work through the possible root causes of what's generating those 404 errors? I'll update the answer with the full explanation once I"Ve had a chance to review your response.
===== COPY BELOW & ADD TO QUESTION =====
Here's the information about my environment that will assist in identifying the root cause of this error:
- Magento Edition: EE or CE
- Magento Version: 1.X.Y.Z or 2.X.Y.Z
- I HAVE or HAVE NOT installed all of the available SUPEE patches listed as impacting the base version of Magento I have installed per the official Magento download repository
This is a list of the patches that are currently installed:
A. SUPEE-AAAA
B. SUPEE-BBBB
C. ....
I am using either:
A. The default Magento Theme that shipped with my edition and version
B A custom theme developed by a 3rd Party
C. A theme I / we developed on our own
If A or B above WE HAVE or HAVE NOT customized the original theme files provided by Magento or th 3rd Party Vendor [please either put the Extension / Template file(s) relating to the Category List display on Paste Bin & add a link to them here]
If you have developed your own custom theme [please also post the file on Paste Bin or diff the changed files and include their source in your update here]
Finally, I went into our Magento Admin Back-End and viewed one of the categories that is listed in the earlier screenshot above with an incorrectly formatted URL and grabbed a screenshot of the the configuration settings of that category so you can compare it with the changes made in the template described above. [Paste the screenshot here]
===== COPY ABOVE & ADD TO QUESTION =====