LETREC requires mutability in the presence of lexical scope. Otherwise it works fine in the way you describe it. Using lexical scope, IS-ODD and IS-EVEN would be bound in parallel and (LAMBDA (X) (NOT (IS-ODD X))) would close over IS-ODD before it is bound, so it would be undefined when applied inside of the outer LAMBDA.

Of course dynamic scoping will bite you earlier or later because of the upward and downward FUNARG problems. See my book (http://t3x.org/lfn/) for lots of entertaining details.