When a node containing a cck_map field is deleted, the corresponding entry in table cck_map isn't deleted.

That's because function cck_map_field in cck_map.module has no handler for 'delete' as an operation; fixed by adding

    case 'delete':
      if ($node->nid) {
        db_query("DELETE FROM {cck_map} WHERE nid = %d", $node->nid);
      }
      break;

to the end of the switch clauses at line 266.

Pete.