Looking at that list, what do you consider "challenging"? Or is this just a list of all games you played? I'll throw some suggestions, somewhat blindly, dunno if they'd exactly constitute "challenging".
Amnesia - as in a more horror-y game. Also, worth playing just because we need more games to take note from there.
Arx Fatalis - you said you played all of the M&M franchis, well this is really similar to Dark Messiah (made by the same guys). Only with more than kicking to it.
Blade of Darkness - in a weird way, it's like Dark Souls - if you are not careful, you'll die. Watch out for traps, a lot of traps. And healing isn't exactly common, killing enemies without taking many hits is preferable. Some even drop a health potion but there is a catch, they may drink it before you kill them.
Disciples - I recommend the second one, since I've played it. It's a turn based strategy like Heroes. Pretty similar but also really cool and stands on its own. Your hero participates in combat, alongside the creatures, and hero and creatures all gain XP, levels and abilities.
Devil May Cry 3 - I still haven't played 4, but this one is pretty cool. In a "learn how do do those combos without thinking" way. The second to last boss is by far the hardest fight I've had in a game. The final boss was easier, even.
Hitman - the series are not on your list, while Thief is. I can't say more than, go fix that. If you're discovered, you could shoot your way out of the situation, but most likely you'll die and/or make everybody really suspicious. Executing the perfect hit is really rewarding, too.
MechWarrior/MechCommander - not bad. MW in particular is a bit unwieldy, due to the control scheme, but really fun to play. If I recall correctly, 4 was released for free a couple of years back.