Maybe there is a way of doing this, but briefly scanning through the relevant functions suggests that I basically have no control over the item being removed, or the call to wc_add_notice to mark is as removed.
As such I ended up with the following fairly simple, but slightly ugly method:
add_action('woocommerce_cart_item_removed', function($key, $cart){
// SNIP - My logic to decide if this item can't be removed by itself
$cart->restore_cart_item($key);
wc_add_notice('This package is tied to another product in your basket.', 'error');
add_filter('woocommerce_add_success', '__return_false');
}, 5, 2);
Basically I restore the item and add an error notice to inform the user that we couldn’t remove it. Then for the remainder of the current request I filter any new success notices to replace the text with FALSE.
The code to display notices uses array_filter to exclude any elements in the list that equate to false, so while a message does get added, it has no text and is not displayed.
Once a basket item is removed, the code path from WC_Form_Handler simply adds the “removed” notice and performs a wp_safe_redirect, so overriding notices at this point should not have any other adverse effects as far as I can see.