Where does authenticity fit into the CIA Triad?

That would still be covered in integrity: creating or deleting data is still a violation of integrity. (This can be seen as a mutation on the overall data set.)

I support David's view that if you had to fit your scenario into one of the CIA categories, integrity would be the appropriate one because you're creating an unintended state thus violating integrity.

But also have a look at the Parkerian hexad which is a popular extension of the CIA triad. It consists of the attributes confidentiality, possession or control, integrity, authenticity, availability and utility. In this model, writing messages in the name of another user would fit into the authenticity category.

Also, you might want to think of the CIA triad mainly as overall security goals. But it's not necessarily a powerful tool to classify specific vulnerabilities.

It doesn't fit. Authenticity and non-repudiation are common extensions to the triad. Data privacy is another one (especially in Europe).

The CIA triad, like any mnemonic, is a useful tool, not a perfect definition. It helps greatly in getting away from a single-minded approach to information security, but there are always issues that it does not cover perfectly.

A well-known extension that explicitly covers Authenticity is the Perkerian Hexad.