Remove Custom Taxonomy Base

I think this is possible, but you will need to keep an eye on the order of the rewrite rules. To help you with this I recommend a plugin I wrote to analyze the rewrite rules (soon available in the repository, but you can download a pre-release).

First of all, these rules are quite generic, and should thus come at the end of the rules list. The default action is to put them at the top, so we prevent the default and add them ourselves. We already have the generic page rules at the bottom, so we should make them explicit and move them to the top by enabling verbose page rules. This is not efficient when you have lots of pages, but I don’t think there is another way to do it now.

add_action( 'init', 'wpse6342_init' );
function wpse6342_init()
{
    // Register your taxonomy. `'rewrite' => false` is important here
    register_taxonomy( 'wpse6342', 'post', array(
        'rewrite' => false,
        'label' => 'WPSE 6342',
    ) );

    // Enable verbose page rules, so all pages get explicit and not generic rules
    $GLOBALS['wp_rewrite']->use_verbose_page_rules = true;
}

add_action( 'generate_rewrite_rules', 'wpse6342_generate_rewrite_rules' );
function wpse6342_generate_rewrite_rules( &$wp_rewrite )
{
    // This code is based on the rewrite code in `register_taxonomy()`

    // This rewrite tag (%wpse6342%) is just a placeholder to use in the next line
    // 'wpse6342=` should be the same as the `query_var` when registering the taxonomy
    //    which is the name of the taxonomy by default
    // `(.+?)` works for a hierarchical taxonomy
    $wp_rewrite->add_rewrite_tag( '%wpse6342%', '(.+?)', 'wpse6342=' );
    // This will generate the actual rewrite rules, and put the at the end of the list
    $wp_rewrite->rules += $wp_rewrite->generate_rewrite_rules( $wp_rewrite->front . '%wpse6342%', EP_NONE );
}