Deeper pipelines have higher clock frequencies but this comes at the cost of lower instructions per clock (IPC). Roughly speaking, asking for a shallower pipe essentially boils down to asking for a lower clock frequency. Deeper pipelines are more complex to build, tricky to validate, not to mention the obvious fact that they consume more area and power, so architects who choose deeper pipelines are doing so only because performance studies show that these pipes are worthwhile.

The branch in this example is essentially random and so pretty much impossible to predict. I would classify it as a pathological case. A modern predictor such as perceptron [1] or even the older tournament predictor [2] is extremely accurate for branches found in real benchmarks.

[1] http://www.cs.utexas.edu/~lin/papers/hpca01.pdf [2] http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-TN-36.pdf

PS. Sidenote about the P4, it achieved the highest SpecINT CPU score among all its contemporary processors so it wasn't the performance disaster some people make it out to be. It's worth noting that SpecINT CPU is has traditionally been the most challenging benchmark in terms of branch prediction requirements. SpecFP CPU for example is full of easy to predict loops.