AFAIK expression trees don't consider two ParameterExpression objects created with identical arguments as "the same parameter".
Without having tested your code, then, that's what sticks out: as I read the first (failing) scenario, you replace all same-named parameters with the first such encountered, but that first encountered parameter is not the same ParameterExpression object as the one you create in your call to Expression.Lambda(). In the second (succeeding) scenario, it is.
EDITED I should add that I haven't used LinqKit's ExpressionVisitor, but as far as I'm aware it's based on code that I have used, in which VisitLambda is not very robust:
protected virtual Expression VisitLambda(LambdaExpression lambda)
{
Expression body = this.Visit(lambda.Body);
if (body != lambda.Body)
{
return Expression.Lambda(lambda.Type, body, lambda.Parameters);
}
return lambda;
}
Note that the body of the expression is visited, but not its parameters. If LinqKit hasn't improved this, that would be the point of failure.