This appears to be a result of the conflict between declaring a non-hierarchical custom taxonomy, and using the post_categories_meta_box (checkboxes) as an interface.
You could call the discrepancy a bug in WP Core, certainly the fact that the conflict is allowed in the taxonomy declaration itself.
The problem seems to be that for your non-hierarchical taxonomy, the checkboxes are rendered with the input “value” = term_id, but the checkbox callback used at post save time stores the value of the checked item as a term name, so you get that integer (the ID) created and stored as a “new” term.
See also this question
Solution for now: just declare the taxonomy as hierarchical if you want to use the checkbox interface.