No, that's the central point I'm getting at--horizontal and vertical DO commute. You can measure both of them at the same time. What doesn't commute is vertical and 45 degrees (or, by symmetry, horizontal and 45 degrees.)
The way to think about this process is the following. We have light coming in with random polarization. This means you can model each photon as being in a superposition of both vertical and horizontal at the same time. The vertical polarizer acts as a measuring device, so it collapses the wavefunction of each photon into either 100% vertical or 100% horizontal. The ones which end up being horizontal get blocked, and the ones that end up being vertical get passed. So each photon coming out of this polarizer is 100% vertical. You can check this by putting it through another polarizer--if it's vertical, 100% of the light will go through (if the polarizer is ideal, of course), and if it's horizontal, 0% will go through. So the light is now 100%, definitively vertical, and 0% horizontal.
Now, if you put it through a 45 degree polarizer, you have to change bases. Instead of thinking in a "X percent vertical and Y percent horizontal" basis, you have to change to a "X percent positive 45 degrees and Y percent negative 45 degrees" basis. Note that these two axes are still perpendicular, just like our original two, we've just rotated. Now, due to the way you transform between these two bases, it turns out that light which is 100% vertical and 0% horizontal can also be viewed as light which is 50% positive 45 degrees and 50% negative 45 degrees. So our beam of light, which we thought was purely one state, can also be thought of as an equal superposition of two other states, +45 and -45. So now, when it goes through the second filter, it again acts like a measuring device, and collapses the wavefunction to one of those two. Just like the first time, if it's positive 45 degrees, it's blocked, and if it's negative 45 degrees, it's passed (or vice versa, depending on how you oriented the plate.) So you will see half of the light transmitted, and half absorbed, just like in the classical description.
This concept is very central to how quantum mechanics works--a system that is purely, definitively, 100% in one state can also be viewed as a superposition of multiple other states, if they don't commute with the first state. It's exactly analogous to how you can think of a vector that goes along the X axis as having only an X coordinate, and a Y coordinate of 0. But there's nothing really special about that vector--if you looked at it in a rotated coordinate system, it would have nonzero values for both components. So nothing is special about one basis or another, you just transform it into whatever basis you need for that problem. The way the state transforms under a change of basis determines its behavior. In this case, the equations for how you transform from one polarization basis into another are what give rise to the classical equation of Malus's Law.