I think I found a counterexample: the germ of the idea
came to me in the shower yesterday morning. Set
d = mu alpha . (<> -o alpha) + 1
and do iteration at sigma := <> -o tau for some tau and
you can get away with weird functions.
So I've been hacking away on a system without alphas
occurring underneath -o on either side, and took out
reduction under lambdas. I think the polytime proof
should go through for this one, and maybe even inference
might be feasible now that I look at it. I think maybe
I could recursively characterize (given the relevant
delta) the effect of replacing sigma with <>^n -o sigma.