We have an issue after importing using Magmi where some product URLs are SEF and others are not.
For example :
we have emptied the table url rewrite and reindex but it does not work.
In addition, we found that by opening the product page in Admin i.e. editing the product and just saving it back. It fixed the url but it's not possible to do this for every product.
Another issue (not sure whether it is related) that the url structure is inconsistent. For example the product url if the product is accessed from the homepage is different from opening it up in the category page.