The AI of computer chess is seriously dumbed down for many players who'd never beat it otherwise.Pacman like all games is set in a world based on rules. I am sure the logic puzzles can be extended without making the game impossible to beat. Its rules are much simpler than chess and yet chess is still possible to beat against a computer that plays by the rules.
There's only so much you can do with Pacman regards ghost movement - how do you propose the ghost AI can be improved in a way which is fair and challenging and different to how it is? We can extend game complexity by having different behaviours from different ghosts etc., but the AI level is fundamentally the same with a few tweaks to parameters. I don't see any reason for it to be different. I don't see any reason to change AI behaviour in the likes of current shooters either (based on my moderate experience). Grunts offer suitable challenge while being eminently beatable. Maybe there's the issue of dumb AI every now and then that sees troops walking into walls or standing around, but those are bugs rather than AI design faults.