It may come as a surprise but when a contact is created as a side-effect of another operation, e.g. qualifying a lead or processing incoming message with contact auto-create in force, pre-validation plugin does not fire at all. It happens when operation performed is a compound message such as QualifyLeadRequest or DeliverPromoteEmailRequest.
This behaviour, unintuitive at first, is by design. The best explanation comes from David “Twice Chartered” Jennaway:
My general starting point is that I expect one message (QualifyLead) to cause one corresponding pre-validation step. If one message is implemented by several operations (Create contact, Create account etc.) then I’d expect one pre-operation step for each operation, so the behaviour you describe is as I’d expect.
Taking this further, in a scenario like this, the data in the message can affect which operations occur. For example, if the lead has no contact fields set (i.e. no name), would you expect an operation to create a contact?
The solution is to either move/copy your logic into pre-validation step of a relevant compound message or move your plugin to pre-operation step.