For me, the measure of whether or not something is cheese is, "Would this actually work in a realistic world that isn't run by a computer AI?" or "Would this fly if you were playing D&D with a real Dungeon Master?" If it fails one test, it's moderately cheesy, if it fails both then it's super cheese.
Most of the things you can "get away with" in these games that end up giving you an unfair advantage or trivializing content only work because the game programming is limited and cannot react or adapt to what you are doing. When you are no longer using the rules of the system, but instead abusing the limitations of programming, I think it's cheese.
That being said, people can play their game however they want. As you said. But for many people, knowing that they did something "legit" is important to them.