As discussed with @Julian, IValidator should be defined formally so we can write tests against things. I'm sure there's other useful things about having it formalized too.
Since it seems silly to require zope.interface for one little interface, the implementation should only be defined if z.i is importable.
Tests against the existing IValidator implementors should be created too.
I'm gonna take a crack at this, let me know if you have input. CC @gazpachoking