Unit testing code that verifies order of method execution
I think your colleagues are correct in that your test looks like it is testing code written as part of your test.  Meaning code that looks similar to the production code, but isn't.  But there are things of value here to test.

You mentioned that your builder has tests around it.  I would think that these "do things execute in order" questions are best answered by testing your builder in different configurations.  the question is simply, "can the builder build things that execute in order".

Secondly, the validation service is a concrete implementation with and interface (abstraction).  You'll likely want to test the concrete implementation because it will probably (unless configured dynamically) have a very fixed set of validation rules that are set for your business needs.  Those tests become, "is my validation service catching all of the currently considered scenarios".