La función de mi verificador de valores debe devolver tanto un valor booleano como un mensaje

Utilice un objeto de retorno más complejo que encapsule ambas preocupaciones. Ejemplo:

public interface IValidationResult {
  boolean isSuccess();
  String getMessage();
}

Esto tiene varias ventajas:

1. Devuelve múltiples datos relacionados en un objeto.
2. Espacio para la expansión si necesita agregar datos adicionales en el futuro.
3. No confíe en el acoplamiento temporal: puede validar múltiples entradas y no obstruyen el mensaje como en la otra respuesta. Puede revisar los mensajes en cualquier orden, incluso en subprocesos.

En realidad he usado este diseño específico anteriormente, en aplicaciones donde una validación puede ser más que simplemente verdadera o falsa. Quizás sea necesario un mensaje detallado, o solo una parte de la entrada no es válida (por ejemplo, un formulario con diez elementos puede tener solo uno o dos campos no válidos). Usando este diseño, puede acomodar fácilmente esos requisitos.

Ninguna de las anteriores, usa una clase de ValueChecker

Primero una interfaz para darle flexibilidad:

public interface IValueChecker {
    public boolean checkValue(String value);
    public String getLastMessage();
}

Luego implemente tantos valuecheckers como necesite:

public class MyVeryEspecificValueChecker implements IValueChecker {
    private String lastMessage="";
    @Override
    public boolean checkValue(String value) {
        boolean valid=false;
        // perform check, updates "valid" and "lastMessage"
        return valid;
    }
    @Override
    public String getLastMessage() {
        return lastMessage;
    }
}

Código de cliente de muestra:

public class TestValueChecker {
    public static void main(String[] args) {
        String valueToCheck="213123-YUYAS-27163-10";
        IValueChecker vc = new MyVeryEspecificValueChecker();
        vc.checkValue(valueToCheck);
        System.out.println(vc.getLastMessage());
    }
}

Tiene la ventaja de que puedes tener muchos verificadores de valor diferentes.

Mi respuesta extiende el enfoque de @ Snowman. Básicamente, cada validación, cada regla de negocio y cada lógica de negocio deberían ser capaces de dar alguna respuesta, al menos en aplicaciones web. Esta respuesta, a su vez, se muestra a una persona que llama. Esto me llevó a la siguiente interfaz (es php, pero la pregunta es de lenguaje independiente):

interface Action
{
    /**
     * @param Request $request
     * @throws RuntimeException
     * @return Response
     */
    public function act(Request $request);
}

La creación de un operador de switch que actúa como una expresión, no como una declaración, hace que el servicio de la aplicación se vea así:

class MyApplicationService implements Action
{
    private $dataStorage;

    public function __construct(UserDataStorage $dataStorage)
    {
        $this->dataStorage = $dataStorage;
    }

    public function act(Request $request)
    {
        return
            (new _SwitchTrue(
                new _Case(
                    new EmailIsInvalid(),
                    new EmailIsInvalidResponse()
                ),
                new _Case(
                    new PasswordIsInvalid(),
                    new PasswordIsInvalidResponse()
                ),
                new _Case(
                    new EmailAlreadyRegistered($this->dataStorage),
                    new EmailAlreadyRegisteredResponse()
                ),
                new _Default(
                    new class implements Action
                    {
                        public function act(Request $request)
                        {
                            // business logic goes here

                            return new UserRegisteredResponse();
                        }
                    }
                )
            ))
                ->act($request)
            ;
    }
}