Answering my own question here - in the end the main cause was that we had a bunch of users with e-mail synchronisation on.
Part of the issue was also the personal setting that creates a contact after there has been email traffic between the contact and the CRM user, but this is no longer possible when email sync is turned off.