For Magento 1.5! Modified Mage_Catalog_Model_Resource_Eav_Mysql4_Url::_getProduct function. This function now contains a boolean that you can set to switch between rewriting the URL's for ALL products and rewriting only the URL's of products that are visible. Idea inspired by Alan Storm's blog on Scaling Magento - http://alanstorm.com/scaling_ma…

Mage_Catalog_Model_Resource_Eav_Mysql4_Url::_getProduct - Magento 1.5.php

<?php

protected function _getProducts($productIds = null, $storeId, $entityId = 0, &$lastEntityId)
    {
        $products = array();
        $websiteId = Mage::app()->getStore($storeId)->getWebsiteId();
        if (!is_null($productIds)) {
            if (!is_array($productIds)) {
                $productIds = array($productIds);
            }
        }
        $selectAllProducts = false;
        
        if(!$selectAllProducts) {
            $visibilityAttributeId = Mage::getModel('eav/entity_attribute')->loadByCode('catalog_product', 'visibility')->getId();
            $select = $this->_getWriteAdapter()->select()
                ->useStraightJoin(true)
                ->from(                    array(
                        'e' => $this->getTable('catalog/product'),
                        'i' => 'catalog_product_entity_int'
                    ), 
                    array('e.entity_id','i.value'))
                ->join(
                    array('w' => $this->getTable('catalog/product_website')),
                    $this->_getWriteAdapter()->quoteInto('e.entity_id=w.product_id AND w.website_id=?', $websiteId),
                    array()
                )
                 ->joinLeft(
                    array('i'=>'catalog_product_entity_int'),
                    'e.entity_id = i.entity_id AND i.attribute_id = ' . $visibilityAttributeId,
                    array()
                )
                ->where('e.entity_id>?', $entityId)
                ->where('i.value > 1') // everything that is not on "Not visible invidually"
                ->order('e.entity_id')
                ->limit($this->_productLimit);
        } else {
            $select = $this->_getWriteAdapter()->select()
                ->useStraightJoin(true)
                ->from(array('e' => $this->getTable('catalog/product')), array('entity_id'))
                ->join(
                    array('w' => $this->getTable('catalog/product_website')),
                    $this->_getWriteAdapter()->quoteInto('e.entity_id=w.product_id AND w.website_id=?', $websiteId),
                    array()
                )
                ->where('e.entity_id>?', $entityId)
                ->order('e.entity_id')
                ->limit($this->_productLimit);
        }
        if (!is_null($productIds)) {
            $select->where('e.entity_id IN(?)', $productIds);
        }

        $query = $this->_getWriteAdapter()->query($select);
        while ($row = $query->fetch()) {
            $product = new Varien_Object($row);
            $product->setIdFieldName('entity_id');
            $product->setCategoryIds(array());
            $product->setStoreId($storeId);
            $products[$product->getId()] = $product;
            $lastEntityId = $product->getId();
        }

        unset($query);

        if ($products) {
            $select = $this->_getReadAdapter()->select()
                ->from(
                    $this->getTable('catalog/category_product'),
                    array('product_id', 'category_id'))
                ->where('product_id IN(?)', array_keys($products));
            $categories = $this->_getReadAdapter()->fetchAll($select);
            foreach ($categories as $category) {
                $productId = $category['product_id'];
                $categoryIds = $products[$productId]->getCategoryIds();
                $categoryIds[] = $category['category_id'];
                $products[$productId]->setCategoryIds($categoryIds);
            }

            foreach (array('name', 'url_key', 'url_path') as $attributeCode) {
                $attributes = $this->_getProductAttribute($attributeCode, array_keys($products), $storeId);
                foreach ($attributes as $productId => $attributeValue) {
                    $products[$productId]->setData($attributeCode, $attributeValue);
                }
            }
        }

        return $products;
    }