So I took Roland's comment and tried to get it integrated into my code. For the tab management it worked well, but for portlet management it was a lot harder. Actually I only have a partial implementation finished. What's missing is the necessary logic to be able to move a portlet in the same tab from one column to another (there are 3 columns a portlet can be in for each tab). The thing that was most important to me was cleaning up the pruning operation. This took some trickery (aka hackery). I think its a better implementation but it does make me a bit nervous. Of course its all still very MySQL only.

Anyways so here goes the final query for moving a tab:

UPDATE user_tabs ut
    JOIN user_tabs ut2
        ON (ut.user_id = ut2.user_id
            AND ut2.id = :id
            AND ut2.pos != :pos
            AND ut.pos >= LEAST(ut2.pos, :pos)
            AND ut.pos <= GREATEST(ut2.pos, :pos)
        )
    SET ut.pos = CASE
        WHEN ut.id = :id THEN :pos
        WHEN ut2.pos > :pos THEN ut.pos + 1
        WHEN ut2.pos < :pos THEN ut.pos - 1
    END
    WHERE ut.user_id = :user_id;

Like I said the pruning operation took some hackery. What I do now is essentially redoing the entire positions for the tabs and all portlets for the given user. If a portlet is marked as to be removed, I update the position to NULL. This way I can easily remove the processed removed tabs and portlets afterwards. The tricky part was in updating the positions for tabs. I update all portlets in the order of the tabs. Of course whenever I start processing the next tab, I need to reinitialize the position counters for the columns. Since I am not aware of any way to do this directly, I created a fake condition that actually just ensures that the counters are reinitialized if the tab_id has changed since the last processed row.

Also note that I have to do two separate UPDATE's, because MySQL does not support JOIN's in UPDATE's together with an ORDER BY. Since I cannot work without the ORDER BY, I had to split things in two queries. This also means that I need to SELECT the tab_id's for the current user, so that I can filter on them in the UPDATE of the portlets, where I do not have a column with the user_id.

$tab_ids = SELECT id FROM user_tabs WHERE user_id = :user_id;

SET @pos := -1;
UPDATE user_tabs
    SET pos =
    (
    CASE
        WHEN is_removed = 1 THEN NULL
        ELSE (@pos := @pos + 1)
        END
    )
    WHERE id IN ($tab_ids) ORDER BY id, pos;

SET @tab_id := 0;
UPDATE user_tab_portlets
    SET pos =
    (
    CASE

        WHEN (tab_id = @tab_id OR ((@tab_id := tab_id) > 0 AND (@poscolleft := -1) >= -1 AND (@poscolmiddle := -1) >= -1 AND (@poscolright := -1) >= -1)) THEN

            CASE
                WHEN is_removed = 1 THEN NULL
                WHEN col = :colleft THEN (@poscolleft := @poscolleft + 1)
                WHEN col = :colmiddle THEN (@poscolmiddle := @poscolmiddle + 1)
                ELSE (@poscolright := @poscolright + 1)
                END

    END
    )
    WHERE tab_id IN ($tab_ids) ORDER BY tab_id, pos;

DELETE ut, utp
    FROM user_tabs ut LEFT JOIN user_tab_portlets utp
        ON (ut.id = utp.tab_id)
    WHERE (ut.pos IS NULL OR (utp.id AND utp.pos IS NULL)) AND ut.user_id = :user_id;

Thanks again Roland for your feedback. Lets see if I find time to also rewrite the other queries.