You can run the following SQL to find out which URLs belong to non-existing products:
SELECT `cur`.`product_id` FROM `core_url_rewrite` AS `cur` LEFT OUTER JOIN `catalog_product_entity` AS `cpe` ON `cur`.`product_id` = `cpe`.`entity_id` WHERE `cpe`.`entity_id` IS NULL AND `cur`.`product_id` IS NOT NULL
... you should see a list of entity objects that are not in
`catalog_product_entity`
EcomDev has a free URL rewriting module ( http://shop.ecomdev.org/url-rewrite-indexer.html ), which I found useful.
EDIT
To answer the question, new URLs are generated, because when reindexing the URLs is done, follow these steps:
Mage_Catalog_Model_Indexer_Url::reindexAll()
... which is a wrapper around:
Mage_Catalog_Model_Url::refreshRewrites
... verification is not performed if the data has been changed. If you need something, you can override this class and rewrite functionality to compare differences.
james source share