How to redirect all unpublished nodes of a certain type
I ended up going with the first option and using the following solution to make sure the redirects never got out of hand:

Basically when a job advert goes down it will get given a 301 redirect. Then I remove every redirect for a job advert older than 3 months.

Hopefully this will remove the worst of the 404 problem because: If Google crawls the link in the three months then it will be redirected and change its index.

If a person comes across it in the three months they'll be correctly redirected and if no-one has bothered to try it for three months then I've probably avoided the 404 problem.

The code just involved calling an extra cron job and then altering a version of the redirect_purge_inactive_redirects(); function.

function redirect_purge_job_redirects(array $types = array('redirect'), $interval = NULL) {
  //set interval in code to 3 months in seconds
  $interval = 7776000;
  $query = db_select('redirect');
  $query-&gt;addField('redirect', 'rid');
  if (!empty($types)) {
    $query-&gt;condition('type', $types);
  }
  //add in condition here to select all redirects 
  //for the job adverts.
  //the path for all the job adverts begins with job
  //so I look for that.
  $query-&gt;condition('redirect', 'job'.'%', 'LIKE');
  $query-&gt;condition('access', REQUEST_TIME - $interval, '&lt;');
  $query-&gt;addTag('redirect_purge');
  $rids = $query-&gt;execute()-&gt;fetchCol();

  if (count($rids)) {
    redirect_delete_multiple($rids);
    watchdog('redirect', format_plural(count($rids), 'Removed 1 inactive redirect from the database.', 'Removed @count inactive redirects from the database.'));
    return $rids;
  }
}