I managed to make him fail by guessing Tian Zhao, the leader of SDC in Call of Duty: Black Ops II
[spoilers, maybe?]
He repeatedly asked if the character was from the Call of Duty series, if it was from the future - I answered "probably", once BO2's storyline involves both past and future and we get to see Zhao in both eras - and if it was from Russia or Europe. I answered he wasn't from Europe and he still guessed Imran Zakhaev and another russian from Modern Warfare games.
His first guess was Menendez himself. Zhao probably isn't evil as I think he is.
Zhao wasn't even in that list he shows us when he misses!