If you open Control Panel > Fonts, do you see the ESRI font files? There should be 73 of them. If you don't see the Esri fonts, that may explain why you don't see them in the Symbol Selector.
As you said the font is not available on the effected system. We install on the system even though it is not showing the fonts again and issue is still pending.
In the font folder after reinstallation the font are not showing.
I would suggest you call Esri Support Services to create a case. The analyst should be able to assist you with this error. Not sure why the complete uninstall/reinstall of ArcGIS Desktop (ArcMap/ArcCatalog) did not fix this issue.
