I think challenge in video games is important at times, but difficulty isn't a prerequisite for an enjoyable (and even lengthy) game. Often, games with shallow and repetitive gameplay benefit dramatically ramp up their difficulty to have more lasting power - but I think fun and immersiveness are crucial to a good game.
People sometimes look back at early arcade games, using them as a benchmark for 'good, but insanely difficult' games. I think their difficulty is often unforgiving, persistent, and simply not fun at all. But 'back in the days', these games often were the norm, and like all childhood memories we only have fond memories of them. Of course, some people still love those games (much like people who can't get enough of Bullet Hell-style games), but in general, people just want to have fun (cue Cindi Lauper).
Game genres do not have that much of an influence in gamers 'craving for more difficult games', because I think all games are unique on their own. Moreover, gamers who prefer a certain genre won't mind a difference in difficulty that much - just because they love this or that kind of game.
Tom Bissell wrote [url="http://www.crispygamer.com/features/2010-01-04/demonic-difficulty-are-most-games-today-too-easy-or-is-demons-souls-too-hard.asp"]a funny article[/url] about the matter, you might want to check it out.