Hmmm, baffling. Got my Safari Hat 7 years ago, don’t remember any problems once I found out about needing alt from other faction to get that last trainer.
A suggestion from TCHAPIN on the Wowhead forums:
The bug (and all this confusion) is caused by the fact that the Taming Kalimdor achievement hides the two starting tamers from the opposing faction, and incorrectly shows the achievement as being completed, when it actually isn’t. You can verify this bug by logging into the Alliance side and looking at Taming Kalimdor. The first two tamers are listed as Julia Stevens and Old MacDonald. Switch to the Horde side, and the first two tamers are listed as Zunta and Dagra the Fierce.
So looking at achievements it’s possible for a faction to see they’ve completed Taming Kalimdor when, in fact, they haven’t. Might be worth double-checking those 4 trainers before opening a ticket.