Just to make sure I understand this right, say we have 3 attributes with 3 levels each. This means that there are 27 total possible combinations. If I go by the formula above, I get: 3 x (9 - 3 + 1) = 24 tasks, which is almost all the possible combinations. If we have 3 attributes, with respectively 2, 2, 3 levels, there would be a possible 12 combinations, but the formula would give us: 3 x (7 - 3 + 1) = 15 tasks.

Am I misinterpreting the formula?

But, researchers now have HB estimation, which can get away with fewer observations and still obtain equally good results as OLS (where OLS is using more observations). Most CVA users (applying HB) would be feeling pretty good with 1.5x as many questions as parameters to estimate (Total_levels - Total_attributes +1).

As Keith points out, one needs to think about whether main effects are enough (as CVA assumes) or interactions are needed. There are power tricks with CVA to estimate interaction effects. It usually involves collapsing two or more attributes into a single attribute, using multiple versions (blocks) of the design (as CVA supports) and HB estimation.