I've been dealing with this problem with around 10k+ products in two store views in magento 1.7.
The URL indexing process took around 30 hours to change its state to ready. Also i found multiple entries of the same product being made in the core_url_rewrite table and the number of rows now reached upto 6500k.
This is causing deadlocks. I tried clearing the locks but that didn't help. Is there a workaround solution for this problem as this is magento core functionality?