Maybe a bit late but this issue is still happening and other users could be affected.
Yoy shoud check your "category_product" table, its almost sure that there are oime ghost registers addresing the id_product with a "0" id_category.
When the importer (on a update import) try to recover the old categories from the product, it will find this "0" id_category and will treat as a new category.