Where Should The Validation Logic Live?

Question

How best can i manage construction of an object graph where complex validation logic is required?. I would like to retain dependency injected, do-nothing constructors for testability reasons.

Testability is very important to me, what does your suggestion do to maintain this attribute of the code?

Background

I have a plain-old-java-object which manages the structure of some business data for me:

class Pojo
{
    protected final String p;

    public Pojo(String p) {
        this.p = p;
    }
}

I want to make sure that p is of valid format because this business object really makes no sense without that guarantee; it should not even be created if p is nonsense. However, validating p is non-trivial.

The Catch

Really it requires complex enough validation logic that the logic should be fully testable in it's own right, and so i have that logic in a separate class:

final class BusinessLogic() implements Validator<String>
{
    public String validate(String p) throws InvalidFoo, InvalidBar {
        ...
    }
}

Possible Duplicate Questions

• Where Should Validation Logic Be Implemented? - The accepted answer is impenetrable to me. I read "be run in the class's native environment" as a tautology, how can validation rules be run in anything other than "the class's native environment"? Point 2 i fail to grok so i can't comment.
• Where To Provide Logic Rules for Validation? - Both answers suggest the responsibility lies with the client / data provider, which i like in principle. However, in my case the client may not be the originator of the data and