Just been reviewing the code saw a todo comment regarding deleting notifications after a comment is deleted - so heres an issue to track.

/**
 * Implementation of hook_comment().
 */
function notifications_comment_comment($comment, $op) {
...
    case 'delete':
      // @todo delete subscriptions for this comment
      break;