Right - in the database table "PageDefinition", there is a column for "Order". I noticed in that column, there were duplicate Order values for multiple pages with the same ParentPageID. Now it occurs to me that, depending on how the data is fetched when the portal is rendered, the tabs with identical Order values may not always be in the same order when gathered. That's why I mentioned moving them up and back down or vice versa, as it may be an issue with the Order values.
If you have access to the database, have a quick peek at the Order column and look at the tabs you're seeing move around.
select * from PageDefinition
where IncludeInMenu = 1
order by [Order]
Because of how the Pages work, I can't really come up with a better answer as to why one user would see something differently than another.
I was able to reproduce what looks like the same issue you're seeing. I set the Order of two items to the same value, and as I refreshed the page, the tabs switched positions occasionally. I also confirmed that the tabs looks differently between users. I also confirmed that moving the pages up and then back down corrected the Order, and also prevented the tabs moving around.
I know it may sound odd, but give it a try and let me know if it works.