If the stages for the last build were modified (added/renamed/removed) then all stage view history for the previous builds is removed. I don't like this behavior. It is not convenient, because often I need view logs for a certain stage of a certain previous build (even if such a stage does not exist in the current build anymore).

If the stages for last build don't correspond to the stages of the previous builds it is not a reason to remove the previous ones. It is still possible to display stages for each build independently. It is not a problem if a certain stage is displayed on different positions in different builds. The bigger problem is if it is not available at all like now.

My proposal is to keep stages for previous builds even if they are different. That is, the stage view history should be not just a matrix, but an ordered list of ordered lists with different size.

Vizualisazion?
Each row can be simply independently rendered (the rows can have different length).
It is possible also to "merge" it and display blank rectangles for whose builds who don't have a certain stage, but it is probably more complicated.