I cannot reproduce what you're describing.
Each time I add a category to a product, the category gets added with a greater product_category_id.
Now, if you're talking only about the display on the back end, it is indeed ordered on the category_id, but not for your modified query which is based on the product_category_id and thus should not have the problem.
The order on the category listing of the products is done by:
$query = 'SELECT b.* FROM '.hikashop_table('product_category').' AS a LEFT JOIN '.hikashop_table('category').' AS b ON a.category_id=b.category_id WHERE a.product_id = '.$product_id.' ORDER BY b.category_ordering';
and should be:
$query = 'SELECT b.* FROM '.hikashop_table('product_category').' AS a LEFT JOIN '.hikashop_table('category').' AS b ON a.category_id=b.category_id WHERE a.product_id = '.$product_id.' ORDER BY a.product_category_id';
in adminsitrator/components/com_hikashop/views/product/view.html.php o that the categories are always displayed in the order they are added. However, as I said above, that doesn't change the fact that they are in the correct order in the database.