Plugin to apply 301 redirections on a per-site basis

We often migrate websites to our WPMU setup and they have crappy URL structure so we improve that along the way.

Doing so breaks pre-existing URLs, so we would create 301 redirections in the .htaccess, but that one is shared with all the sites.

We are looking for a suggestion / plugin that would allow us to map old URLs with the new ones to avoid losing SEO when migrating+improving websites.

Looking forward to your ideas!