Upgrading from 1.9 - What to do about indexed URLs?

I am currently in the process of upgrading from 1.9 to 2.65 and it is going very well in the tests I am doing so far.  However, there is one thing I cannot find anyone asking about.  What to do about the fact that *all* URLs change moving from 1.9 to 2.x.  For my client, his site has been actively indexed by Google and others.  I cannot upgrade without addressing the existing pages to provide proper redirection for them.

I would use the IIS7 Rewrite module to do the redirection.  However, this site is still hosted on IIS6, so it's off to the 3rd party dance.

What has everyone else done?

No worries. 2.X automatically handles all old URLs and redirect users to the pages with the new URL format. You can test on our demo site