Java Static Method vs. a Singleton in Validator

an anti-pattern in all cases to use static methods rather than singletons

This is not true. In some cases static methods are absolutely fine, in others not.

Here are some examples from widely used libraries when it is perfectly fine to use static methods:

• CollectionUtils in Apache Common Collections
• StringUtils in Apache Commons Lang
• FileUtils in Apache Commons IO
• ClassUtils in Spring Framework
• PropertiesHelper in Hibernate

There are no strict criteria in what case static method can be used or should not be used. For some developers this is a matter of their personal preferences, to use static methods as much as possible, or vice versa, to avoid static methods as much as possible.

If you have no strong preferences, you may consider following criteria to decide.

1. How likely it is that that the functionality provided by the needs to extended or modified in the future? If you see that it is very likely that some methods may need to overridden for some context, then it makes sense to use non-static objects. If it is unlikely (e.g. it is unlikely that the method that compares two strings safely, without throwing NPE), then it is fine to put such functionality in a static method.
2. How likely it is that there will be more than one class with similar functionality? Is it likely that you may need some generic functionality that uses different implementations in different contexts (e.g. polymorphism may be needed)? For instance, serializing an object to JSON might be a static method. But if you expect that very likely serialization to YML, XML, CSV, PDF or some other formats will be needed, it makes sense to put make such functionality non-static.
3. How easy would it be to test such functionality? In some cases testing can be easy, e.g. testing a methods that compares two strings without throwing NPE. In other cases it may be pretty complicated, e.g. if such method is called from another code that is being tested.

To your case with MyValidator: I would suppose that later on you may need more than one validator and some generic logic that iterates over list of attributes, determines validators for each attribute and applies them. With static methods it will be very hard to implement it. Where as with non-static methods it may be much easier. For instance, it would be easier to define a generic structure of such classes as following:

public interface Validator<T> {
  boolean isValid(T target);
}

Then applying such may be very compact:

for (...) {
  validator = findValidatorForObject(obj);
  // No need to check the type: String, Integer, ...
  if (!validator.isValid(obj)) {
    ...
  }
}

I believe you're setting up a false dichotomy in static methods vs. singletons. Singletons often create problems because they hold state that is hidden from the clients of the classes that access the singletons. But as an alternative to static methods they would not hold state.

Another alternative is for you to define an interface that can be filled with your static method in production code and a mock in testing code:

interface Validator {
    boolean isValid(String string);
}

class ClassThatUsesValidator {
    private final Validator validator;

    public ClassThatUsesValidator(Validator validator) {
        this.validator = validator;
    }

    public void methodToTest(String value) {
        if (validator.isValid(value))
            ...
    }
}

// production code
ClassThatUsesValidator obj = new ClassThatUsesValidator(MyValidator::isValid);

// test code
Validator mock = mock(Validator.class);
when(mock.isValid("foo")).thenReturn(false);
ClassThatUsesValidator testObj = new ClassThatUsesValidator(mock);
testObj.methodToTest("foo");
assertThat ...

This way you are avoiding a singleton, using a static method and are still able to mock it for testing.