Reason for such behavior lies in wp_insert_post function. When you look at its code, on line 3319 you’ll see this line:
$post_name = wp_unique_post_slug( $post_name, $post_ID, $post_status, $post_type, $post_parent );
And what this function does is (straight from Codex):
Computes a unique slug for the post, when given the desired slug and
some post details.
And it ignores taxonomies. If the post type is hierarchical, then it allows same slugs, if posts have different parents. But if post type isn’t hierarchical, it just makes sure that the slug is unique.
And it makes sense – you can reassign post to another category and that will create conflicts. Also default WP permalink structure doesn’t use category as part of URL.
But… There is a way to change it (although it’s a little bit risky…) At the end of that function it returns:
return apply_filters( 'wp_unique_post_slug', $slug, $post_ID, $post_status, $post_type, $post_parent, $original_slug );
So you can use wp_unique_post_slug hook and modify the computed slug.