The pattern WordPress uses to recognize pages is (.+?), which will match anything, but is not greedy, so it allows you to put something at the end. The following code works for me in WordPress 3.0.1: it places the extra pattern at the second-to-last place of the list, because the final pattern is so generic it will match every URL:

add_filter( 'page_rewrite_rules', 'wpse7243_page_rewrite_rules' );
function wpse7243_page_rewrite_rules( $rewrite_rules )
{
    // The most generic page rewrite rule is at end of the array
    // We place our rule one before that
    end( $rewrite_rules );
    $last_pattern = key( $rewrite_rules );
    $last_replacement = array_pop( $rewrite_rules );
    $rewrite_rules +=  array(
        '(.+?)/([0-9]+)/([^/]+)/([^/]+)/?$' => 'index.php?pagename=$matches[1]&id=$matches[2]&fname=$matches[3]&lname=$matches[4]',
        $last_pattern => $last_replacement,
    );
    return $rewrite_rules;
}

Be aware that pages, like any post, can also be split into multiple pages with the <!--nextpage--> snippet, and the normal URL for that is /pagename/2/, which might be confusing when you also have /pagename/3/jan/fabry/ where the 3 is an ID. You can change the pattern to include an optional page number at the end, so this can become /pagename/3/jan/fabry/2/ where the final 2 is the page number, and the first 3 is the ID.

If you are changing the rewrite rules I recommend my rewrite analyzer plugin (soon in the repository, but get the current version via Dropbox), it helps you debug these things.

The pattern WordPress uses to recognize pages is (.+?), which will match anything, but is not greedy, so it allows you to put something at the end. The following code works for me in WordPress 3.0.1: it places the extra pattern at the second-to-last place of the list, because the final pattern is so generic it will match every URL:

add_filter( 'page_rewrite_rules', 'wpse7243_page_rewrite_rules' );
function wpse7243_page_rewrite_rules( $rewrite_rules )
{
    // The most generic page rewrite rule is at end of the array
    // We place our rule one before that
    end( $rewrite_rules );
    $last_pattern = key( $rewrite_rules );
    $last_replacement = array_pop( $rewrite_rules );
    $rewrite_rules +=  array(
        '(.+?)/([0-9]+)/([^/]+)/([^/]+)/?$' => 'index.php?pagename=$matches[1]&id=$matches[2]&fname=$matches[3]&lname=$matches[4]',
        $last_pattern => $last_replacement,
    );
    return $rewrite_rules;
}

Be aware that pages, like any post, can also be split into multiple pages with the <!--nextpage--> snippet, and the normal URL for that is /pagename/2/, which might be confusing when you also have /pagename/3/jan/fabry/ where the 3 is an ID. You can change the pattern to include an optional page number at the end, so this can become /pagename/3/jan/fabry/2/ where the final 2 is the page number, and the first 3 is the ID.

If you are changing the rewrite rules I recommend my rewrite analyzer plugin (soon in the repository, but get the current version via Dropbox), it helps you debug these things.