This article is an (incomplete) list of the most difficult, and/or competitive single player games with useful scoring systems. By a competitive game I mean a game with a high skill cap and well balanced, useful scoring system by which skilled players can measure themselves with on a leaderboard. This means they cannot be excessively undermined by stat grinding, save/reloading, imbalanced game mechanics, imbalanced exclusive items, or anything that allows the player to substantially mitigate a game's difficulty.
This list does not contain games with repetitive, grinding, unbalanced, skill-less, or extremely random difficulty. It also has no 'player defined' challenges.
Finally, don't pretend you'd be able to complete these challenges or compete in the high score lists 'if you had no life' - you need skill in addition to practice, just like any competitive game or activity.
Some genres (FPS, Fighters, Driving, etc.) are typically built for multiplayer and aren't mentioned here because the AI in such games usually makes a poor opponent. Some of the most competitive/high skill cap multiplayer games are already famous with large tournaments and audiences - Street Fighter, Counterstrike, Starcraft, etc. Difficult single player games are less well known and so this list is dedicated to them.
If you think I've missed something, feel free to let me know, and I will likely update this list. I don't have a lot of experience with some of the of genres listed here so I welcome your advice if you are a skilled and knowledgeable gamer.
Good shoot em ups follow the formula of complex but fair bullet patterns, intricate skill based scoring systems, auto adjusting rank-based difficulty, and extra challenges for the top 5-10% of skilled players who can complete the game on 1 credit, such as a 2nd loop or a true last boss. Even one bullet connecting with your ship is the kiss of death, so precise movement is vital. Shoot em ups are competitive by nature, due to their nearly limitless skill caps, open ended high scores and the fact that playing a 'perfectly scored' game is often beyond the reach of even the best players.
Aside from the Cave games listed below that are both difficult to 1cc and score on, there are some games that are not as difficult to 1cc with a low score, but still difficult to get a top score on, like Ikaruga or Espgaluda II.
Mushihimesama Futari 1.01 or 1.5 (Ultra Mode). Available for X360 region free.
http://www.youtube.com/watch?v=ZKYxM1WRvL8 (stage 5 ultra)
http://www.youtube.com/watch?v=0VY-qcGgaCU (stage 5 ultra boss/tlb)
Dodonpachi Dai-ou-jou (2nd loop).
http://www.youtube.com/watch?v=FtFkpldJSpY (original version)
http://www.youtube.com/watch?v=B_ah2ah2QaA (black label version)
Ketsui (ura loop).
http://www.youtube.com/watch?v=X9Rlj6jMOC0 Stage 2-4 ura loop (aka special round)
http://www.youtube.com/watch?v=jKWXubTH5jA Stage 2-5 ura loop (aka special round) and true last boss
Death Smiles Black Label (999 mode)
Mushihimesama (Ultra Mode)
The most difficult games in this genre are the ones heavy on action and light on adventure. This sub-genre of action/adventure started (afaik) with the release of Devil May Cry and continued on to Ninja Gaiden, Bayonetta, and beyond. The precise frame-by-frame combat mechanics, deep combo system, unpredictable enemies, extra mission modes, well designed hit/hurtboxes, and competitive scoring system make for a very skill based experience. Hideki Kamiya (DMC, Bayonetta, Viewtiful Joe, God Hand) and Tomonobu Itagaki (Ninja Gaiden) are the two heavyweight developers in this genre.
Ninja Gaiden Black for Xbox (Master Ninja Mode).
Ninja Gaiden II for Xbox 360 story and mission modes (Master Ninja difficulty).
Devil May Cry 1,3 (Dante Must Die Mode w/ all SS ranks).
Devil May Cry 4 (Dante Must Die Mode w/ all SSS ranks).
Bayonetta (Non-Stop Infinite Climax Mode w/ all PP medals).
Godhand (Hard mode, no deaths/continues aka no gold subtracted from total at end of stage). This game isn't as difficult as the others unless you go with a player defined challenge due to the lack of a real scoring system.
Metal Gear Rising S on Revengence difficulty + gold medals on all VR missions.
Platformers require coordination and skill, but are generally less heavy on combat and more about timing jumps and avoiding environmental hazards. This is one of the most nostalgia-tainted genres due to the overabundance of platformers the NES. Old NES games like Battletoads, Zelda 2, Mega Man, etc. are easy compared to what's out there now.
Kaizo Mario World
Viewtiful Joe 1 and 2 (all perfect scores, hardest difficulty)
I Wanna be the Guy/Boshy/other variants. Retro themed platformers designed to be extremely difficult.
Super Monkey Ball (Master levels on one credit aka no continues).
Action/First and Third Person Shooter:
Armored Core: Last Raven (all S ranks)
Vanquish (God Hard mode, score attack, challenge modes)
Pinball games are still around and still hardcore with solid mechanics, 'one credit only' play, scoring systems, trick shots, and wizard modes. The wizard mode is usually activated when the player completes all of the normal scoring modes/minigames/events on one credit. There are still annual pinball tourneys held across the world with fierce competition.
The Simpsons Pinball Party (wizard mode)
One of the most complex and in depth modern pinball games. "The Simpsons Pinball Party is famous for its extremely hard-to-reach wizard mode, the Super Duper Mega Extreme Wizard Mode. There are very few players in the world who have reached it. Even some of the world's best have failed to accomplish it."
Lord of the Rings Pinball (wizard mode)
"The wizard mode (Valinor Multiball) is said to be one of the hardest to reach to date (only being topped by The Simpsons Pinball Party)".
Guitar Hero Series
This popular rhythm game features some extremely difficult challenges that few players in the world have mastered.
Beatmania IIDX Series
A DJ based rhythm game that defines finger-twisting agony. Some of the most difficult tracks will have you wondering whether the players have grown an extra finger or three. Honorable mention to Pop 'n Music.
Good puzzle games have simple yet difficult to master mechanics, with solid and balanced scoring systems. They have nearly limitless skill caps due to added stress factors like time limits. Some complex puzzle games may leave your brain tied in a knot or have extremely tough action sequences.
Tetris: The Grand Master 3 and 4. Sure you've played tetris, but have you cleared Tetris: The Grand Master 3?
I don't have a lot of experience with this genre. Probably missing some things.
Ace Combat 4,5,Zero,6 (Ace or Ace of Aces difficulty, S ranks).
The Sky Crawlers: Innocent Aces (Ace difficulty, S ranks).
I don't have a lot of experience with this genre. Likely missing lots of entries.
ADOM, Nethack, Crawl, other modern PC roguelikes.
Wizardry IV: Return of Werdna.
Role Playing Games:
Any suggestions that don't involve grinding?