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...
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:
(same product, both urls work) This once again has a valid URL key that is not a duplicate, and yet can not index. Why?