No matter how skillful or challenging you make it the battling is still going to become repetitive and boring. Once you get the hang of it I mean. A lot of people on this forum sight dark souls as being challenging. Once you get the hang of the gameplay though its all a lot of boring soul farming for upgrades.
Now multiply that by X number of years playing an MMO? I don't see what you're expecting them to do exactly.
What of anything no matter how creatively designed in a game will not become repetitive or boring in a game if you repeat it over and over? The meat and potatoes of most rpgs is battle and story questing. No matter how ingeniously or lazily those two portions are designed. You always see some variation, be it slight or great amongst rpgs. Dark Souls is or isn't difficult depending on the player. No game is really difficult if you have knowledge, practice, and patience. Dark Souls does however require relatively constant movement across a three dimensional axis. One of the most common complaints about traditional mmos is that the environment is three dimensions. But many require little to no movement, just stand still and spam rotations.
I'm one of those big Dark Souls fans you speak of, so I felt like I had to chime in.
The thing that keeps Dark Souls combat interesting is multiplayer. You can easily step into 3-on-1 combat where you're the 1 against 3 well-armed opponents whose only purpose in life is to cheaply gank you. To that end, there's effectively no limit to the difficulty, unless you can master even that, but even the best players suffer under such unfair conditions. (Pulling off a win, however, is one of the best trollface moments you can have...)
However, there is a limit to multiplayer: your level. You can't be invaded by characters who are much higher in level in level than you are, and conversely, you can't invade characters who are much lower in level than you are. You are complete control on how much you level your character, however, and leveling is the only way to raise your stats. Once raised, there's no going back.
So the fun, and replayability, is in building a character with certain specifications. One that's strong enough to use the equipment and/or magic you'd like to use, but not so high level that you place yourself out of multiplayer range (there are 712ish levels you can raise your character depending on your starting class, but most stick with level 120 as the max or your ability to invade/be invaded falls off sharply). Doing this means you have to live without certain amenities as well (you may have strong stats for weapons, but that doesn't leave a lot left over for magic, health, equipment weight, etc.), so it's a carefully considered process.
The process of building your character does involve going through the same story all over again, and, of course, once you get used to it, it does become routine. But because you're leveling your character in a new way, not unlike leveling a new job from level 1 in FFXI, your experience will be slightly different. Your first playthrough may have involved hacking and slashing your way with melee weapons, but if you're building a mage, you'll have to learn how to fight at range a lot more. You may have built a tank the first time and were able to soak a bit of damage, but if you're going for a stealthy, sneaky type character this time, you'll have to learn to dodge blows more often. Different weapons have different movesets and there's a wide variety to choose from which also keeps it interesting.
All that said, I'm not sure how well this translates into actual MMO material, other than to say that mutliplayer alone can add to replayability and player motivation for no more reward than the chance to beat a challenging foe. I should caution that action combat tends to have issues when you're dealing with a lot of players simultaneously hacking at each other. The perceived fairness of such combat can come into question when complaints arise that you only won because the lag was favoring you, so it's not 100% without its flaws. To that end, menu/action bar driven combat tends to resolve itself a bit more evenly when lag strikes since any character is presumed to be defending themselves automatically rather than sleepily accepting a fatal stab to their back.