It's an old thread, but if anyone is interested in fixing this behaviour, then it happens because of this inside Classes/Product.php.
// mark all products whose position within category (might) have changed as modified
$return &= Db::getInstance()->execute('
UPDATE `'._DB_PREFIX_.'product` p'.Shop::addSqlAssociation('product', 'p').'
INNER JOIN `'._DB_PREFIX_.'category_product` cp ON (cp.`id_category` = '.$idCategory.' AND cp.`id_product` = p.`id_product` AND cp.`position` >= '.$position.')
SET p.`date_upd` = "'.$now.'", product_shop.`date_upd` = "'.$now.'"
');
If you are on PS 1.6, you can fix it by commenting out the last SET line
$return &= Db::getInstance()->execute('
UPDATE `'._DB_PREFIX_.'product` p'.Shop::addSqlAssociation('product', 'p').'
INNER JOIN `'._DB_PREFIX_.'category_product` cp ON (cp.`id_category` = '.$idCategory.' AND cp.`id_product` = p.`id_product` AND cp.`position` >= '.$position.')');
/* SET p.`date_upd` = "'.$now.'", product_shop.`date_upd` = "'.$now.'" */
The behaviour happens for all versions of PrestaShop, not just 1.6. It's because the category position ID's of all the products in the same category as the product you remove, has to be updated.