I remembered that I thought I was being awfully clever re-using application nodes aggressively - turns out this worked fine for non-recursive code or code that used the native Y-combinator in my reduction engine but failed when I used a Y defined directly in the lambda calculus. I removed this "optimization" and the problems went away.

What I always remember is that the idea as to what was causing the problem came as a complete bolt from the blue when I was thinking about something else - perhaps the first time that something like that happened to me, but certainly not the last!