Why delete old redirects? I have many, MANY redirects (thousands).  Most just redirect the system (node/12345) url to the friendly one - but we also have a lot of others.

I have Drupal set to never delete old redirects after they haven't been accessed for X amount of time, but the mere presence of the option to do so makes me think there's a legitimate reason I may want to.

Is there a lot of overhead?  Or is it simply to keep the list manageable?  Do people typically delete them, and if so, what's the time frame?  Six months?  A year?
Whether to keep redirects is an SEO question. Do you have good search results on Google which you don't want to loose. Or you have external sites or even print stuff that point to your old URLs. Then you have to keep them.

If all this is not true, you can safely delete you old redirects.

About the DB:

The redirects are stored in the url_alias table. It has two indexes for the mapping from nid to redirect url and from redirect url to nid. This means that reading is fast even if you have thousands of redirects.

If you are creating a lot of redirects this can get slow. But this will not hit you for a few thousand redirects. If you have millions you have to dive into MySql details (or whatever DB system you are using) and find what you can do about it. Since you are only adding records to the DB table, there's a lot of DB tuning stuff that can help you.