Although we're using Apache instead of IIS, we had similar performance worries about large numbers of redirects. We implemented the following system:
Any pages that need to be redirected would normally generate a 404 Not Found error since they no longer exist, so we only process rewrites on 404's. This means we don't have any performance penalty for regular requests.
Once a page generates a 404, we pass the request to our 404 controller, which checks a (cached) db table and renders a redirect header to the browser. If no matching page is found we render the regular 404 page.
Since redirects are stored in a table we can integrate them into our cms, e.g. providing an option to manage all redirects to a page from the page's properties. Or automatically checking for redirects which point to non-existing pages.