Doesn't that only apply if the bulk of the energy of the pump is being lost to fluid resistance in a fixed-sized pipe? In the case of New Orleans levy pumps, the vast majority of the energy used by the pumps would be used to increase the potential energy of the water pumped (i.e. pumping water uphill).
Yes, you are right that the power increase is to compensate for head loss. When you are pumping water into Lake Pontchartrain, you have to operate the pump at a head to compensate for the difference in height being pumped and for the head loss in the pipes. The pressure of the water exiting will be same as the medium that it is entering (not at a much higher pressure). If at any point in time it is higher, the flow would increase until it was equal at exit. When flow increases, head loss goes up. Therefore, there is a balance between flow rate, head loss, and pump head. Head loss (friction in the piping and the energy required to change the direction of water in horizontal turns of the pipe) is still the controlling factor. The power needed is still proportional to the cube of the volumetric flow rate.
I just realized I didn't answer your question very well. The VHP to 123 rule only applies for the difference accounted for by head loss. You are right that the part of the pump head that accounts for the difference in height to be pumped is unaffected.
I think it is unlikely that the pumping to Lake Pontchartrain is going to need much head to account for a large difference in height. I would assume that the designers would would go for the most efficient design for draining rainwater. This means that they would never be pumping higher than a ~10 ft difference in height. I would assume that the largest fraction of the pump head is going to be for head loss.