Steps

• Confirm with client the urls to be redirected
• Install path_redirect module
• Identify which urls can be generated from node/{nid}
• Identify which urls are views to be created
• Any remainder on the list not covered by node/{nid} or views, discuss with client possible solutions, and come to an agreement
• Analyze pattern of old url generation, find a logical pattern, usually can be obtained from tables in the old database
• Create a script that uses the mapping of drupal's node table to old database (created earlier) to populate path_redirect table

Details

With path redirect module, all their old links would work and redirect properly 301 to the new items.

To test path redirect, they can go to the admin page /admin/build/path-redirect, or to really test, they could alter their hosts file to point to the beta server, and see what happens when they look up an old url.

  $rid = db_next_id('{path_redirect}_rid');
  $old_url = 'music-reviews';
  $new_url = 'reviews/music';
  db_query("INSERT INTO {path_redirect} (rid, path, redirect, type) VALUES (%d, '%s', '%s', '%s')", 
$rid, trim($old_url, '/'), trim($new_url, '/'), '301');

Regeneration of url aliases

If the customer changes their mind about the url structure, no need to regenerate most of the redirect links. The path redirect module works together with the url alias table to provide the correct url.

Delete the url aliases from url_aliases table using the menu option to delete aliases for all nodes, or with sql to delete certain aliases.

DELETE FROM url_alias WHERE src LIKE 'node%' AND dst LIKE 'movies/%';

Note if the new pathauto pattern is similar or identical to the old url's populated in path_redirect, then please patch pathauto with http://drupal.org/node/261615 so that if the url auto-generated is identical, delete the row from path_redirect instead of creating the url in url_alias with -0 added.