This is a clean install of EE 1.13.1 not an upgraded site.
I am facing this issue with a group of skus in my catalog...
www.MYSITE.com/catalog/product/view/id/189576/s/**url-key**/category/293/
I have checked the rewrite tables for this and there are no rewrites for it. It is as if it is keeping that url, and will not index it to a clean url.
Secondly there are products like this:
www.mysite.com/catalog/product/view/id/188662
(same product, both urls work) This once again has a valid URL key that is not a duplicate, and yet can not index. Why?