I am creating a new
Entity contact = new Entity("contact");
contact["fullname"] = "New contact";
contact["lastusedincampaign"] = DateTime.UtcNow;
Looks like CRM ignores
lastusedincampaign attribute like it does a few other during create operation. If you do not want to perform create/update operations at the same time, why don't you create a temporary workflow that would run asynchronously and update the field's value? This way async server takes most of the load and the record creations are faster.
Side note 4k records is not an awfully lot of records to perform a create/update simultaneously, I have worked with records in the tens of thousands and CRM never bottle necked on me.