Using an enumeration is fine if you want to restrict the possible states of invalidation. That will allow your UI etc to handle each possible state. If you have many, variant, states from your validation system then I'd recommend just creating a validation class that holds the relevant information and returning that from your validatior e.g.:
static IValidationInfo Validate(ILicense someLic)
{
// Implementation
}
interface IValidationInfo
{
IEnumerable<LicenseErrorCodes> KnownErrors { get; }
IEnumerable<string> WierdErrors { get; }
}
Creating classes is a lightweight process so the performance considerations compared to something like the 'out' solution suggested are going to be minimal.
Edit: Additionally, I'd also recommend against using exceptions for validators. At least to me, a validator should be designed to take input and validate it. Let consumers deal with any invalid data errors it spits out without having to do so in a try{} catch{} block. Exceptions should only really be used for unpredictable/external issues that can't directly be handled by consumers e.g. File access issues or COM invalidation.