Modified Mage_Catalog_Model_Resource_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_magento_at_copious

Mage_Catalog_Model_Resource_Url_getProduct.php

<?php

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

        $rowSet = $adapter->fetchAll($select, $bind);
        foreach ($rowSet as $row) {
            $product = new Varien_Object($row);
            $product->setIdFieldName('entity_id');
            $product->setCategoryIds(array());
            $product->setStoreId($storeId);
            $products[$product->getId()] = $product;
            $lastEntityId = $product->getId();
        }

        unset($rowSet);

        if ($products) {
            $select = $adapter->select()
                ->from(
                    $this->getTable('catalog/category_product'),
                    array('product_id', 'category_id')
                )
                ->where('product_id IN(?)', array_keys($products));
            $categories = $adapter->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;
    }