many apps that work with lots of media files have this option. Final Cut Pro 7 probably has the best one, but so do Adobe Premiere and Ableton Live.
whats crucial are several features:
1. option to show only the missing file in question while browsing the "locate files on disk" dialog
2. option to automatically search for other missing files in that same folder
3. option to retain the same relative folder structure while searching automatically (for when a big folder with many subfolders changes location)
these three things in conjunction can fix complicated playlists in just a few clicks.
i can provide screenshots for useful ideas.
there is an external tool called ListFix that is some help, but a proper integrated feature would be awesome.