However, when setting the annotation at class-level, manually performing the required reflection and string validation on the entity inside isValid(), it only takes 0.5 seconds to complete validation for all 72,000 entities.

That one is interesting, why do you use reflection in your class-level constraint? I'd expect you could access the entity state via normal field/getter accesses?

For sure it'd help to see your entity and constraint definitions and how you invoke validation.