Fixes the catalog url rewrite indexer in Magento 1.7.x-1.9.x

magento_url_rewrite.patch

diff -rupN mage_org/app/code/core/Mage/Catalog/Model/Url.php src_shop/app/code/core/Mage/Catalog/Model/Url.php
--- mage_org/app/code/core/Mage/Catalog/Model/Url.php   2013-11-19 00:48:25.679009391 +0100
+++ src_shop/app/code/core/Mage/Catalog/Model/Url.php   2013-11-19 00:49:24.188005601 +0100
@@ -643,13 +643,24 @@ class Mage_Catalog_Model_Url
                 $this->_rewrite = $rewrite;
                 return $requestPath;
             }
+
+            // avoid unnecessary creation of new url_keys for duplicate url keys
+            $noSuffixPath = substr($requestPath, 0, -(strlen($suffix)));
+            $regEx = '#^('.preg_quote($noSuffixPath).')(-([0-9]+))?('.preg_quote($suffix).')#i';
+            $currentRewrite = $this->getResource()->getRewriteByIdPath($idPath, $storeId);
+            if ($currentRewrite && preg_match($regEx, $currentRewrite->getRequestPath(), $match)) {
+                $this->_rewrite = $currentRewrite;
+                return $currentRewrite->getRequestPath();
+            }
+
             // match request_url abcdef1234(-12)(.html) pattern
             $match = array();
             $regularExpression = '#^([0-9a-z/-]+?)(-([0-9]+))?('.preg_quote($suffix).')?$#i';
             if (!preg_match($regularExpression, $requestPath, $match)) {
                 return $this->getUnusedPath($storeId, '-', $idPath);
             }
-            $match[1] = $match[1] . '-';
+            $match[1] = $noSuffixPath . '-'; // always use full prefix of url_key
+            unset($match[3]); // don't start counting with a possible number in the url_key
             $match[4] = isset($match[4]) ? $match[4] : '';

             $lastRequestPath = $this->getResource()

See https://github.com/magento/bugathon_march_2013/issues/265 for details.
Update: DexterDee in the ticket above noted that the previous patch had some side effects. This updated patch still feels like duct tape but at least it seems to be free of the mentioned side effects. It also fixes url key duplication for categories now. You might need to truncate core_url_rewrite once for full effect.