-fno-full-laziness fixes the space leak issue in your iterative deepening example. Yes, and I think it has been mentioned that the flag is a blunt weapon as it affects the whole module...
This isn't a problem with laziness. It's a problem with performing a time optimization which is a space pessimization. In the absence of the "optimization" there is no problem.
How come it isn't the problem with laziness?! Recall, that pure call-by-name calculus is observationally undistinguishable from the call-by-need (i.e., lazy) calculus. The only reason to have laziness is to avoid recomputations of argument computations should an argument be used more than once -- at the cost of taking memory to store the result of the first evaluation. Thus "performing a time optimization which is a space pessimization" is exactly what laziness is all about -- as the article mentioned earlier argued. Laziness isn't an absolute good -- it is a time-space trade-off, which is not always beneficial.