Like I thought, it didn't have anything to do with the code as such but the issue was as follows:

Salesforce itself also has it's logic to determine if the "IsExternallyVisible" flag should be true or false.
You can find an explanation of their logic here:

http://releasenotes.docs.salesforce.com/en-us/summer15/release-notes/rn_service_emails_case_feed.htm

What is important to know is that the code of Salesforce for the IsExternallyVisible flag executes between the "before insert" and "after insert" event.

We didn't know that at first and logically, our logic to set the IsExternallyVisible field was being launched in the "before insert" handler.

So, in the end, causing the Salesforce logic around the IsExternallyVisible to be the boss instead our own custom logic...

So, how we will fix it is either:

- executing the same logic but in the after insert. (meaning we will have to re-query the records cause those from the trigger context would be read only)
- or, executing the logic as a future method

In my eyes, this is very strange behaviour of Salesforce and in any case not handy. They should at least put this a bit more clear in the documentation. Will definitely log a case for this.

UPDATE: I assume the logic will also have to be executed in the "after update" for the case where someone would have first saved an email message as a draft...