(self-answer)

###Simplified the API

You were right, the API was too verbose so I drasticlly simplified it to. It now presents itself like that:

    [Fact]
    public void Simplified()
    {
        var rules =
            ValidationRuleCollection
                .For<Person>()
                .Reject(b => b.Null(x => x).Hard())
                .Reject(b => b.NullOrEmpty(x => x.FirstName))
                .Accept(b => b.Pattern(x => x.FirstName, "^cookie", RegexOptions.IgnoreCase))
                .Accept(b => b.When(x => x.FirstName.Length > 3));

        var results = default(Person).ValidateWith(rules);

        Assert.Equal(0, results.OfType<Information>().Count());
        Assert.Equal(1, results.OfType<Error>().Count());

        
        Assert.ThrowsAny<DynamicException>(() => default(Person).ValidateWith(rules).ThrowIfValidationFailed());
    }

I was not able to incorporate the ROP here this time but the many other ideas where very helpful. Here's the summary:

###Changes

There are only two main extensions Accept that enforces a rule and Reject that negates it (internally) so there is no need for other extensions prefixed with Not.

I also liked @Flater's idea from the other question by @Henrik Hansen where it was suggested picking something more general than IsTrue/IsFalse etc. I decided here to use When. All other extensions have only one overload now. Consequently I could rename Match to Pattern for RegEx.

The last extension, or rather a modifier is called Hard. This one yields a different rule, one that when failed aborts the validation. This also means that I now have two rules which are descendantes of the abstract class ValidationRule<T, TContext>:

public class Hard<T, TContext> : ValidationRule<T, TContext>
{
    public Hard
    (
        [NotNull] Expression<ValidationPredicate<T, TContext>> predicate,
        [NotNull] Expression<MessageCallback<T, TContext>> message
    ) : base(predicate, message) { }

    protected override IValidationResult CreateResult(bool success, string expression, string message)
    {
        return
            success
                ? (IValidationResult)new Information(expression, message)
                : (IValidationResult)new Error(expression, message);
    }
}

public class Soft<T, TContext> : ValidationRule<T, TContext>
{
    public Soft
    (
        [NotNull] Expression<ValidationPredicate<T, TContext>> predicate,
        [NotNull] Expression<MessageCallback<T, TContext>> message
    ) : base(predicate, message) { }

    protected override IValidationResult CreateResult(bool success, string expression, string message)
    {
        return
            success
                ? (IValidationResult)new Information(expression, message)
                : (IValidationResult)new Warning(expression, message);
    }
}

When evaluated they return one of three possible results: Information, Warning, Error.

public class Information : ValidationResult
{
    public Information([NotNull] string expression, [NotNull] string message)
        : base(expression, message) { }
}

public class Warning : ValidationResult
{
    public Warning([NotNull] string expression, [NotNull] string message)
        : base(expression, message) { }
}

public class Error : ValidationResult
{
    public Error([NotNull] string expression, [NotNull] string message)
        : base(expression, message) { }
}

An internal API uses it to break the validation:

    public static ValidationResultCollection<T> ValidateWith<T, TContext>(this T obj, IImmutableList<IValidationRule<T, TContext>> rules)
    {
        return obj.ValidateWith(rules, default);
    }

    private static IEnumerable<IValidationResult> Evaluate<T, TContext>(this IImmutableList<IValidationRule<T, TContext>> rules, T obj, TContext context)
    {
        var result = default(IValidationResult);
        foreach (var rule in rules)
        {
            yield return result = rule.Evaluate(obj, context);
            if (result is Error) yield break;
        }
    }

There is also a new ValidationResultCollection that replaces the tuple I used previously:

public class ValidationResultCollection<T> : IEnumerable<IValidationResult>
{
    private readonly IImmutableList<IValidationResult> _results;

    public ValidationResultCollection(T value, IImmutableList<IValidationResult> results)
    {
        Value = value;
        _results = results;
    }

    public T Value { get; }

    public IEnumerator<IValidationResult> GetEnumerator() => _results.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    public static implicit operator T(ValidationResultCollection<T> results) => results.Value;
}

I use it to chain extensions for throwing exception:

default(Person)
    .ValidateWith(rules) // <-- ValidationResultCollection
    .ThrowIfValidationFailed(); // autocast to T or throw

Generating messages internally still has to be improved but as far as the main API is concerned, I'm happy with it.

End-users can add thier own extension to b. It is a ValidationRuleBuilder<T, TContext> that lets them modify the validation expression: (like I use it for

    public ValidationRuleBuilder<T, TContext> Predicate(Func<LambdaExpression, LambdaExpression> expression)
    {
        _predicate = expression(_predicate);
        return this;
    }
    

I use this too, e.g. for Reject, that Negates the expression:

    public static IImmutableList<IValidationRule<T, object>> Reject<T>
    (
        this IImmutableList<IValidationRule<T, object>> rules,
        Func<ValidationRuleBuilder<T, object>, ValidationRuleBuilder<T, object>> builder
    )
    {
        return rules.Add(builder(ValidationRule<T, object>.Ensure).Negate().Build());
    }