The following code does the job:
/**
* After Deleting User we have to delete all his annotations too
*/
function annotate_user($op,&$edit,&$user,$category=NULL) {
  switch ($op) {
  case 'delete':
    db_query("DELETE FROM {annotations} WHERE uid = %d", $user->uid);
    break;
  }
}


And here are some additional lines to complete the annotate_nodeapi with a "delete"-functionality (see post from dshaw):

function annotate_nodeapi(&$node,$op,$teaser,$page) {
  global $user; //move this to top
   ...
    break; //don't forget this break !
  case 'delete':
    // delete annotations from all Users of this node
    db_query("DELETE FROM {annotations} WHERE nid = %d", $node->nid);
    break;
  }
}