This transpired to be that be related to boolean attributes in CRM. If you do an 'update' using an API and you are updating a boolean with the value it already has, so true to true, then CRM doesn't record that in the Audit against that record. It records other data types when they are updated with the same value, but not boolean's for some reason.
So what was happening is that there are booleans in our trigger, but because it didn't look like the field was update, by looking at the record audit, we didn't know it was the boolean field causing the trigger.
Annoying but good to know.