I guess you should use your function on the hook woocommerce_add_to_cart instead of template_redirect

I guess you should use your function on the hook woocommerce_add_to_cart instead of template_redirect

Your function works fine for me. Try an alternative methow which also works:

    add_action('template_redirect', function () {
        $product_id = 29690;
        foreach( WC()->cart->get_cart() as $key=>$item){
            if($item['product_id']==$product_id){
                WC()->cart->remove_cart_item( $key );                   
            }

        }
        // $product_cart_id = WC()->cart->generate_cart_id( $product_id );
        // $cart_item_key = WC()->cart->find_product_in_cart( $product_cart_id );
        // if ( $cart_item_key ) WC()->cart->remove_cart_item( $cart_item_key );
    });

double check your $product_id and possibly var_dump something to refine debugging