I've recently encountered the phenomenon in which new/edited contact workflow rules are triggered when moving a contact record from one account to another. I'm surprised I have not noticed this before. I was updating contacts via the Web API, changing their account affiliation, and to my surprise some e-mails were sent out because a workflow that triggers on "When a record is created, or when a record is edited and did not previously meet the rule criteria" for contacts" fired off. I also saw that just changing an contact's account within Salesforce (using the web UI) has the same effect.
I assume this means that "new contact" in Salesforce means "contact is new to an account"?
Is this true? Is there a way to keep such workflows from firing? I can assure you that the rule criteria has nothing to do with the contact's account. Such a change should not be firing the workflow.