What to do with unattached logos and header uploaded via native wordpress uploader?

You could add an ID as post_parent to the attachment of the header image via wp_update_post() (even though this seems to be a very very hacky way to do it!)

The tricky part is to get the ID out of the attachment URL; fortunately Rarst solved this issue long time ago, so you can manually add get_attachment_id() to your functions.

Next you’ll have to assign an ID as post_parent; everytime you’ll save the header image the selected header image will be attached to this special ID.

add_action( 'admin_init', 'attach_header_image' );
function attach_header_image() {
  if ( isset( $_POST['default-header'] ) ) :
    $header_image_url = get_header_image();
    $header_image_id = get_attachment_id( $header_image_url ); // function via https://wordpress.stackexchange.com/a/7094/32946
    $args = array(
      'ID' => $header_image_id,
      'post_parent' => 1 // assign header image to this ID
    );
    wp_update_post( $args );
  endif;
}

Nevertheless this seems to be a tricky way to solve the issue and it would probably superior to write an exception for the delete function…

Debugging Infos:

• echo get_header_image() should output the link to the current header image URL (only true if a header image is defined)
• echo get_attachment_id( $header_image_url ) should output the ID of the attachment page which should be equal to the ID of the attachment page you can see in Media (/wp-admin/post.php?post=123&action=edit); make also sure to copy and paste get_attachment_id() function from Rarst to your functions!
• the if-statement containing default-header should check for the name of the checked input header field, which will be saved via $_POST