After trying to hack the new expression visitor class in .NET 4.0 to fit my needs I finally just gave up and wrote a new one from scratch. I did not need the rewriting capabilities of the FCL implementation as I am going directly from an expression tree to an object model. Here are the key features I needed to make this happen:

1. Ability to control which nodes are visited next. I 'm using the approach of having different visitors for different parts of the expression. For example I have a select visitor that just handles the IQueryable methods, a where clause visitor that handles the where expression (Unary and binary expressions only) and a visitor to handle expressions that stem from constants or from properties on an entity. This composition greatly simplifies things and makes the visitors reusable. When I hit a point where I want to pass the torch to a different visitor I want to be able to specify that I don't want the current visitor to continue visiting a particular child node. You can do this manually with the current implementation but why not just tell the visitor which nodes you want it to skip and let it handle that?
2. Need to know what the parent was. Sometimes the parent node can effect how the child is processed. For example if the parent of an expression is a binary expression I need to handle it a little differently. Currently you have no information about the parent expression.
3. Ability to pass along state to visitors of children. I needed to be able to pass along state or a lambda from parent to child in order to build up my object model. I tried a dictionary approach with the current implementation but this was hacky. Not to mention that I didn't want to be doing a ton of dictionary lookups.

So I put together an expression visitor that enables all these features and its made things much easier:

https://gist.github.com/780050

Here are a couple of examples:

Each virtual method has a counterpart that allows you to control what child expressions are visited. For example the VisitMethodCall method has the following overload (In addition to the default):

protected void VisitMethodCall(MethodCallExpression node, TState objectState, TState argumentsState, 
                               bool visitObject, bool visitArguments, params Expression[] argumentsNotToVisit)

Here you can control what is visited as demonstrated by the following implementation:

protected override void VisitMethodCall(Context context, MethodCallExpression node)
{
    // ...
    VisitMethodCall(node, context.State, context.State, true, true, node.Arguments.Skip(1).ToArray());
}

Here we're visiting all the children but skipping every parameter except the first one as we are handing those (Not shown).

We may also need to know what the parent was, as in this example:

protected override void VisitMember(Context context, MemberExpression node)
{
    if (!context.HasParent || context.Parent.IsBinaryLogicalOperator()) //...;
    else //...;
}

Here we need to know if the member expression itself is a predicate (i.e. x => x.Active) or part of a binary logical operation (i.e. x => x.Active == true). In my implementation these two scenarios are handled differently so I needed a way to check this.

The last thing is passing of state. Here I have a visitor for the where clause as follows:

public class WhereVisitor<TItem> : ExpressionVisitorBase<Action<Operand>> {...}

The generic type argument is the visitor state. The state in this instance is an action that has one parameter, an Operand (The Operand type is irrelevant, just an example). This allows us to pass a lambda to a child expression visit method which in turn can pass in some state. This doesn't have to be a lambda, it can be anything that you want passed around from visit to visit.

protected override void VisitBinary(Context context, BinaryExpression node)
{
    // ...
    var operand = // ...;
    context.State(operand);
    
    VisitBinary(node, 
        x => operand.Operator.LeftOperand = x,
        null,
        x => operand.Operator.RightOperand = x,
        true,
        false,
        true);
}

In this example we are creating an operand and passing it into the parent lambda. We are also specifying lambdas that will be passed to the visitor methods that evaluate the children. As you can see they are building up an object model.

In conclusion there are two major things I've learned so far:

1. If there is a lot of friction using the built in expression visitor, write a custom one from scratch that fits your needs. You can look at the one in the FCL with Reflector or the one I have linked above as an example. It's a bit of work to do but I've found it's a much simpler and cleaner approach and will save you headaches in the long run.
2. Go from an expression tree to an object model then from the object model to the domain language (i.e. TSQL). I've found that going directly from an expression tree to a domain language gets complicated very fast, especially when you want to add optimizations. Splitting it up into two steps greatly simplifies things. NHibernate does this as well.