What is The Gift

Because you are not submitting to God's will hard enough.

By the rules as written, that player is correct. In fact, a character with all four Ars Goetia is not particularly likely to have The Gift. The character has Infernal powers, and The Gift is associated with Magic.

Some sort of evil aura would be a really appropriate Flaw for the character, but they do not necessarily have it.

This is correct. When you need a quick, game-mechanical answer, this is how to decide.

Probably not? According to Mythic Locations the Mercurian priests had a ritual to grant the Gift. That alone seems to say it's not a charism. True Faith is the charism, of which the Gift is a poor reflection.

The Gift is of the Magic Realm and IMO it's an alignment to the Magic Realm. Being Gifted saves you from Warping from strong Magical Auras and sets you apart from the mundane (i.e. it gives you social penalties that unfortunately apply to everything). Why and how this alignment with the Magic Realm happens is anybody's guess, though like many other things in Ars Magica it's probably related to Warping on the part of the parents.