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][1] (soon in the repository, [but get the current version via Dropbox][3]), it helps you debug these things.

  [1]: https://wordpress.stackexchange.com/questions/3606/a-tool-to-analyze-rewrite-rules/3608#3608
  [3]: http://dl.dropbox.com/u/7057637/monkeyman-rewrite-analyzer.zip