Logged In: YES 
user_id=593130

"   def f(x): eval('x') works as expected and
    def f(g): eval('lambda x: g(x)') does not. Why?"

For the same reason
  def f(g,s): return eval(s)
 f(lambda x: x, 'lambda x: g(x)')(1)
and
  def g(x): return lambda: eval('x')
do not 'work'.  eval is a builtin C function whose behavior 
depends on its arguments (including the somewhat magical 
defaulting to globals(), local()) and not on its lexical position.

" Both are evaluated at the same time and use
the same environment to look up their variables."

No, the lambda in your second example introduces a new local 
namespace that is different from the one passed in.

" The fact that the 'g' variable in the second case is not evaluated
immediately does not affect its scoping"

The delay and change of scoping are correlated. Evaluation is 
delayed because g is inside a lambda function def which 
introduces a new local scope which does not contain g, even 
though the original one did.