Hi **@Simon Blackbourn:**

While I was writing my answer but before I could post it @Bainternet jumped in with a great answer too. He took a slightly different approach but his works equally as well as mine. Still, since I'd already written mine when I saw his I'll submit mine as an alternate for you to consider.

###Uses Direct SQL: `$post_id = $wpdb->get_var($sql)`
My solution uses direct SQL which is often not the best approach but I feel it is fair here because of this SQL's simplicity *(and is thus unlikely to break in the future)* and because for your needs there is no benefit to using the comparatively heavy `get_posts()` with all its need to process hooks since your needs are one-off for your specific site.

###Uses Direct URL Parameters: `$_GET['lid']`
Additionally I chose to use direct access to `$_GET['lid']` instead of first creating a `query_var` because query vars are part of the standard WordPress query architecture that is use by the underlying URL rewrite system, and for your use-case you are explicitly not leveraging the WordPress query architecture. Instead you need to capture an actual query parameter passed on the URL so I think there isn't really a need for the overhead of adding a query var *(although truth be told using a query var doesn't hurt, and it works fine too.)*

###Uses the `'parse_request'` Hook
Lastly I did like @Bainternet use of `'parse_request'` hook; it runs before WordPress' default MySQL query, so you don't have to run a MySQL query you will just throw away yet it runs after the `'init'` hook which means (most) hooks that allow plugins to modify permalinks will have been added thus giving you the correct URLs for your redirects.
    
###Place in `functions.php` 
You can place the following code into your theme's `functions.php` file:

    add_action('parse_request','oldsite_redirect',0);  // 0=before (most) 'parse_request' calls
    function oldsite_redirect() {
      if (isset($_GET['lid'])) {
        global $wpdb;
        $sql = "SELECT post_id FROM {$wpdb->postmeta} " . 
               "WHERE meta_key='lid' AND meta_value='%s'";
        $sql = $wpdb->prepare($sql,$_GET['lid']);
        $post_id = $wpdb->get_var($sql);
        if ($post_id) {
          $permalink = get_permalink($post_id);
          if ($permalink) {
            wp_safe_redirect($permalink,301);
            exit;
          }
        }
      }
    }

Again, either solution will work; @Bainternet's or mine; your choice which to use.