I haven't played it, but there is a game called Smart Kobold that tries to up the AI difficulty as far as it can reasonably go. In some sense, I think it satisfies your criteria. The punishing difficulty is what makes it rewarding, and it accomplishes it through AI rather than making creatures harder to kill or do more damage.

I do agree with your statement in the vast majority of cases. Ultimately, fun trumps everything else when it comes to games (though what counts as fun is subjective). Even Dark Souls, which many (most) gamers consider difficult, is not difficult because of unbeatable AI. It's full of patterns (indeed, that's how you get better at the game: you recognize and respond correctly to those patterns).