This is an old issue that has never been properly solved. The original issue has been closed due to lack of testing.

Website I am running started having this issue, and we have verified that:

• the issue exists in the newest Joomla (3.4.5),
• the patch below solves the issue.

We are using this patch in production on a high-traffic website. All credits for the patch should go to Michal Michaláč, who seems to be the author of the original patch.

GitHub does not allow me to attach a patch, so here it is, pasted:

--- table.php.orig  2015-10-28 17:44:49.199224888 +0100
+++ table.php   2015-10-28 17:46:52.161204224 +0100
@@ -1367,6 +1367,11 @@
            throw new UnexpectedValueException(sprintf('%s does not support ordering.', get_class($this)));
        }

+        // Speedup by SQL optimalization
+        if ($this->_db->name == 'mysql')
+            return $this->reorderMysql($where);
+       
+        // Default (slow) reorder
        $k = $this->_tbl_key;

        // Get the primary keys and ordering values for the selection.
@@ -1408,6 +1413,47 @@
        return true;
    }

+
+    /**
+     * Method to compact the ordering values of rows in a group of rows
+     * defined by an SQL WHERE clause.
+     *
+     * @param   string  $where  WHERE clause to use for limiting the selection of rows to compact the ordering values.
+     *
+     * @return  mixed  Boolean  True on success.
+     *
+     * @link    http://docs.joomla.org/JTable/reorder
+     * @since   11.1
+     */
+    protected function reorderMysql($where = '')
+    {
+        $k = $this->_tbl_key;
+        
+        $this->_db->setQuery('set @num = 0');
+        $this->_db->execute();
+        
+        $query = $this->_db->getQuery(true)
+            ->update($this->_tbl)
+            ->set('ordering = @num := @num + 1')
+            ->where('ordering >= 0')
+            ->order('ordering');
+ 
+        // Setup the extra where and ordering clause data.
+        if ($where)
+        {
+            $query->where($where);
+        }
+        
+        // Warning: Unpatched version of JDatabaseQuery->__toString ignores 'order' to update query.
+        // Then query must be built from string like this:
+        //$query = "update {$this->_tbl} set ordering = @num := @num + 1 where ordering >= 0 " . $where? (" and " . $where): "" . " order by ordering";
+        
+        $this->_db->setQuery($query);
+        $this->_db->execute();
+ 
+        return true;
+    }
+
    /**
     * Method to move a row in the ordering sequence of a group of rows defined by an SQL WHERE clause.
     * Negative numbers move the row up in the sequence and positive numbers move it down.