I can accept that the genre rather limits possibilities for story agency. Any significant story deviation would quickly end you up with hundreds of diverging storylines, which isn't feasibly doable for any dev studio, and attempts to automatically generate fitting stories have so far been... less than compelling.
Zul may even make some sense - we had good reason to assume he was no good, but the Horde needed the Zandalari, who didn't know. As long as they didn't pick up on it, there wasn't much to be done since they were still wary of outsiders.
On the other hand, the PC should have been well enough aware that something's not right here even for the low-int classes with little understanding of deceit. Rogues and classes that require smarts just to learn have absolutely no excuse for falling for that nonsense. The whole retarded saturday morning mustache twirling just adds the crap cherry on the shitpile. The scenario had no way of being believable pretty much from the start.