Custom Theme Want To Remove One Category From All Displays

The only solution I could imagine is removing, rewriting, replacing the meta box.

// First remove the original one
function wpse21483_remove_catbox()
{
    remove_meta_box( 'post_categories_meta_box', 'post', 'side' );
}
add_action( 'admin_menu', 'wpse21483_remove_catbox' ); // not sure about the hook

function wpse21483_new_catbox()
{
    // re-define - take a look at /wp-admin/include/metaboxes.php
}
// Hook the new one
add_action( 'add_meta_boxes', 'wpse21483_new_catbox' );

Edit: Maybe you can use a the filter for the categories dropdown

function wpse21483_alter_catbox( $output )
{
    global $current_screen;
    $id = $current_screen->id;
    // abort if not on post screen
    if ( $id !== 'post' )
        return;

    // search/replace the category
    return $output;
}
add_filter( 'wp_dropdown_cats', 'wpse21483_alter_catbox', 10, 1 )