Before I address the kinds of considerations that go into object creation, let's first address the motivation behind your question: the phrase "Always Valid Domain Entities". This phrase is, at best, misleading, and makes little sense in the context of DDD. This should be apparent for two related reasons:
The first is that it implicitly shifts your focus away from the behavior of the system, instead, asking you to consider validation only in terms of state. While superficially this may seem to make sense (of course validation is in terms of state!), you must remember that the fundamental principal of DDD is that a system is modeled according to behavior. The motivation for this is quite simply that the context, or the business process itself, is often an important consideration when determining whether or not some piece of state is valid. Modeling a system in this way can greatly reduce it's complexity.
This brings us to the second reason, which is in regard to the practical requirements such a system would entail. In order to create a system of "Always Valid Domain Entities", it would require one to model every single permutation of state according to the business processes in which they arethe state is used. A simple example can illustrate the limitations of this:
Rules:
Customermust be over 18 to registerCustomermust be under 25 to qualify for discount on registrationCustomermust be over 25 to make reservation
The first thing you should notice is that all of these rules (like nearly all rules) apply to some business process. They don't exist in a vacuum. These rules would be validated on customer.Register() and customer.Reserve(). This results in a much more descriptive and declarative paradigm because it's clear where rules are executing.
If we wanted to model these rules such that it results in system of "Always Valid Domain Entities" we would need to partition our Customer into Registrar and Reserver entities. And while that might not seem so bad for this example, as rules become more complex and abundant you will end up with an explosion classes like this that represent state "within" some context or process. This is simply unnecessary and will inevitably create issues when two such objects are dependent on the same slice of state.
Additionally, something like Customer c = new Customer() is a bad place to throw an exception because it's unclear what business rules might apply. Which brings us to our final discussion.
I am just going to come out and go as far to say that there should be zero validation of business rules happening in constructors. Object construction has nothing at all to do with your business domain, and for that reason, in addition to the reasons above concerning context and coherence, all business rules should be enforced within an entity's method bodies (it's likely methods are named after business processes right?).
Furthermore, "newing" up an object is not the same thing as creating a new entity in your domain. Objects don't come out of nowhere. If there are business rules regarding how a new entity can come into your system, then it should be modeled in your domain. Here is some further discussion on the topic by a true master http://udidahan.com/2009/06/29/dont-create-aggregate-roots/