How do I know when another contributed module deletes a block?
There is no hook fired in delete of block, as you can see in the list of block hooks here block.api.php.

There is a topic in Drupal forum here.

I think the best way to handle this is by hook_form_alter something like.

/**
 * Implements hook_form_alter().
 */
function YourModule_form_alter(&amp;$form, $form_state, $form_id) {
  if ($form_id == 'block_custom_block_delete') {
    // You get all information here of the concerned block in $form.
  }
}