Magento core_url_rewrite table excessively large

Question

I've noticed a large amount of reports that this table itself can become extremely cluttered, I'm running a site with ~5000 SKUs and ~250 categories (single-store) and a resultant core_url_rewrite table of over 600,000 lines and over 500MB large which is insane.

This can slow down site performance and result in a very bulky database. I've done some digging and found quite a few posts regarding this, most notably:

• Core_url_rewrite bug: Massive amount of duplicate url’s for each product generated on index
• Magento Commerce - Bug Tracking - Issue #29020

//These links have been removed since the implementation of the new boards

Now I understand that the table can be truncated and reindexed, but this doesn't solve the problem, it just prolongs the issue from happening again.

From what I understand, part of the issue is products which have the same url key based on the product's name, thus resulting in indexed links.

A fix mentioned is:

app/code/core/Mage/Catalog/Model/Url.php on line ~807:

Change:

 if ($product->getUrlKey() == '' && !empty($requestPath)
       && strpos($existingRequestPath, $requestPath) === 0
 ) 

To:

 if (!empty($requestPath)
       && strpos($existingRequestPath, $requestPath) === 0
 ) 

But even this does not completely resolve the issue.

My question is as follows:

If you have experienced this issue, have you managed to set up an effective, logical & efficient algorithm which does not involve "managing" the issue repeatedly, but actually resolving the matter once and for all?

Would really appreciate some insight into this.

BTW: Please do yourself a favor and check what your table is looking like right now, you may be experiencing this issue and the performance impact as a result thereof without even knowing it - I didn't.

Edit: I have been in contact with www.Nexcess.net (a Magento platinum hosting partner) and they have confirmed that they have had clients request that their core_url_rewrite table requires truncation as a result of being too bulky.

A big worry of mine is the SEO impact that this may have, which is why I'd like a solution as opposed to procrastinating the issue from arising again.

Update: Nexcess mentioned that with the duplicate products within the table it may actually be hurting SEO as it is.