Sounds like this "move" process doesn't move the product to a new category so much as link it to the category. I say that because if it were truly moved, there should be no remnant/reference of the product to a previous category.
The table that contains the information I think you are trying to remove is the products_to_categories table.
Thinking:
Code:
delete from products_to_categories where products_id in (select products_id from products_to_categories where categories_id=15) and categories_id != 15;
Where the categories_id of the "disabled" category is 15.