This is a point where I have greatest sympathy with game designers and especially game AI designers.
I am not the greatest computer gamer, but I am pretty good at a lot of games, especially the various board games I have played with folk over the years. I have been accused of "cheating" at various games just for playing smart, especially if I am using knowledge of rules and foresight to set myself up in some advantageous position. The funniest was a Monopoly game, where I had to ask what particular move was cheating when every one else at the table was watching. (And they watch closely; nit-picking rules and game process is a fanatic hobby in my family and a source of great enjoyment.) I never got a specific answer and ended up letting it slide so as not to start a big argument. Whatever I had done was just not fair and I had cheated, even if it was legal. It just goes to show it is not just AI perception. It is a perception people have of all sorts of opponents and challenges. "That's not fair!" is a big line and attitude. "Cheat" is a magic word in both real life and gaming forums. It can be used to immediately polarize a discussion and make scapegoats to account for someone's frustration.
I have to take the whole "you cheat" with a sense of humor. I am both a stickler for rules and one that bends them to almost broken. I can't really blame folk for frustrated misconceptions. And, I try to play games with the idea that everyone should have fun of some sort. However, as a game designer, you don't have such luxury. You have to meet the whole different perceptions thing from all sides at once. Myself, I don't mind if the AI plays with handicaps. I find a middle level difficulty that works for me and concentrate on having fun. As far as a game designer is concerned, I'm easy. As far as the others go, I can only advise game designers to know in their heart of hearts that the user community itself "cheats" by loudly demanding impossible or contradictory things. It won't make the challenge any easier, but it should be emotionally satisfying. In the long run, that seems to be the main purpose of yelling the word "cheat" in the first place, emotional satisfaction and release.
Me, I cheat and gain my emotional satisfaction and release by loving my family more and more. It may sound all gushy to you, but it works for me. It also frees me to be even nastier when we play board games like Risk. 