Just Cause 2, which has thousands of items, hundreds of locations, a thousand square kilometers, tons of quests, and far too many collectibles/destructibles that AREN'T documented in any way (identified as "something to do" in a settlement, etc.). It's almost impossible (if not flat out impossible) to 100%-complete this game without any sort of guide or 3rd party mod tool for the PC version.
Made more fun by the fact that, at least in the PC version, it's impossible to get beyond 99.95% completion because of two things: a missing water tower, and a bug that does not reward you any items upon completing the final optional faction mission (no matter what that mission is). Fortunately, there's a mod available that will restore both the tower and the missing item boxes.
Some of the various collectibles spread throughout the Grand Theft Auto games are so tucked away and well-hidden that locating them all by oneself seems like a near-impossible task. One egregious example appears in San Andreas, which has a sidequest in which you must take pictures of photograph icons spread throughout the game. While several of these are damned well-hidden, the most ridiculous one is located on the roof of a random, innocuous building. You can only see the photograph icon by flying an airplane on the roof itself, and not from on the ground or from any nearby buildings, although a player in the know can take the picture itself from the ground.
To be fair, one of the flying missions does pass over those buildings. And it's quite likely a mission you'll have to repeat a few times. Damn plane...
Here's the secret: the snapshot locations glow with a strong pink light at night. You can see it from an in-game kilometer away. If you ever stop and wonder where that shine comes from (it has no apparent source), you'll zoom in with whatever you have and see the icon. Problem solved.
Some of the properties you buy in Vice City have associated missions that you need to complete in order to make them profitable. You're never told how to make the strip club profitable. It requires you spend $500 on a dance in the back room. Not only does this mean putting down the controller and doing nothing for several minutes, but it also makes no narrative sense- why does this suddenly make the club start generating money?
Grand Theft Auto V has the first dog in the series, Chop. He is only trainable through the iFruit app for iOS and Android, and his ginormous piles of doggy poo can only be cleaned via said app. The only hint the game gives you of how to do that is a short info bubble in the upper left of the screen, very much a blink and miss it situation. To make matters worse, very few devices using the latter OS can run the app. Have an Android device that can't run the app? Tough luck.
In The Godfather 2 there are several Made Men waiting for hire around the cities who start with two specialties compared to the one of most and better levels of weapons training. The problem is that the places they can be found are usually not obvious.
La Noire frequently gives the player several possible leads to follow up at various points. However, sometimes one lead will provide evidence that can trap a suspect in a lie in a later lead; if you follow the leads out of order, you may be unable to challenge a suspect's lies. The game never warns you, it falls entirely to the player to figure out in advance, which is sometimes nigh-impossible without psychic foresight or a strategy guide. Luckily, neither the game nor any individual case becomes Unwinnable by botching an interview.
When trying to find any of the collectibles, this becomes Guide Dang ItThe Game. Every single one of the collectables are impossible to find without a guide: such as the Gold Movie Reels that are so out of the way you can go the entire game without finding one and Landmarks that only appear if you happen to drive by them. Though this is nothing compared to finding all 95 vehicles, where aside from 15 secret cars located on your map, they are pretty much left up to luck finding them. It also doesn't help that most of them look the same.
Minecraft in general. You aren't told how to make tools or other crafted items, nor are you told using a bed changes your spawn point after you die. The Xbox 360 version eases this slightly by show you what items are needed to craft other items and what their functions are.
Terraria does its best to avert this for early game players. If you show your Guide an item, he will tell you what can be crafted from it. In addition, the game will also tell you what is necessary to qualify a structure as a house for NPCs, so more of them can spawn. However, some mid- and late-game events can be hard to figure out without a peek at the wiki.
Finding the Floating Islands is often so ridiculously time-consuming that many players simply cheat by downloading a map viewer. For those who view this as against the spirit of Terraria, good luck. Floating Islands can spawn anywhere above a certain altitude, and it's incredibly difficult to tell where they can be found without building a skybridge (which takes a ton of resources) or flying around in the sky with a Gravitation Potion.
Sunflowers can block the Corruption and stop it from spreading.
Water Bolt, a spellbook hidden in the dungeon. It's hidden on the bookshelves in the dungeon, of which there are dozens, with nothing to draw attention to it at all. The only hint you get to its existence is that, if you're right on top of the shelf containing it, your mouse cursor will change when you mouse over it.
Dwarf Fortress suffers from this at times. The controls are easy enough to pick up once you get used to the UI, but the in-game help is sparse and erratically updated. The wiki, the forum and a third-party strategy guide form the majority of the game's actual documentation.
In Dead Rising there are tons of survivors in the game. Now while they aren't rudimentary to the plot to get 100% completion for it you need to rescue (practically) ALL of them. Not only are they completely stupid and horrible at following you, some of them AREN'T shown to you by Otis and you have to find them yourself. However you don't even have all the time in the world to look for them as they have TIME LIMITS when they spawn and despawn. And the final Guide Dang It catch? There can only be 8 possible survivors at once and no more will spawn if the mission will push the survivors over 8. This mechanic was never explained or hinted at in the game.
One of the Assassination missions requires you to drive up on a specific location in "a muscle car," but doesn't tell you which models are considered "muscle cars." (If you're wondering: Bootleggers, Hammers, Hammerheads, and Phoenixes count.)
The Collectible Finder ability doesn't reveal the locations of Stunt Jumps or Barnstorms. Fortunately, doing those are not needed for Challenges or Achievements/Trophies, and they only give cash and Respect that can be earned elsewhere.