An enemy which appears randomly, with no specific point (save one or two to introduce them). Typically takes the form of an Elite Mook which is dangerous early on but much less so when they are encountered later in the game. Comes in several flavors which may overlap with one another;
The Wanderer:Patrols a specific area in the game. They may actively stalk the player or they might just move randomly until they find them. Distinguished in that the player may never even meet them.
Schrodinger's Encounter: The player will always encounter the enemy - it's just a matter of when. The point at which they turn up is fixed but decided randomly from several potential points ahead of time (typically when the game begins). Distinguished from The Wanderer in that the player won't be able to avoid them.
Triggered Encounter: This often takes the form of a boss or Boss in Mook Clothing. It appears only if the player acts in a very specific manner. A specific version of this is Stalked by the Bell, where the enemy appears if the player lingers too long in one area.
Fake Roamer: The game pretends that this enemy is actively stalking you or wandering around but it really turns up at specific points in the game. You can identify it by the fact that it always turns up in the same place no matter how many times you play that part of the game.
In .hack//G.U., the Doppelganger, which is a shadowy copy of the party leader (in the player's case, Haseo) that is always 8 levels higher than the player (unless you are at the volume's max level), wanders the area you are in by warping around, but only in fields. One turns up in the field if you don't fight for a certain amount of time, or if you use the keyword "Moonlight", which ensures that there is a Doppelganger in that field. You can run around the field and never find him, or he may be right next to your starting point. Doppelganger can be quite a terrifying opponent, whether or not you actually encounter him. If he finds you, the screen begins to flash red and scary music plays as he stalks towards you; if he doesn't, one can get the feeling of being watched. To make it even more unnerving, it's also moving around even while you're in a battle and can actually join in on a battle you're currently fighting if it gets too close.
Several areas in World of Warcraft have overpowered enemies patrolling them as type 1. The most infamous example is the Sons Of Arugal, level 20 elites that patrol an area used by players of levels 10-19.
The most well-known, however, are the Devilsaurs in Un'goro Crater. Because they become visible at the same effective range as other monsters despite being fifty feet tall, they have gained a reputation for having taken Ninja levels. See also the That One Boss and Boss in Mook Clothing entries.
The game also uses type 3 a lot, where specific enemies will only appear if you are on a particular quest.
All of the mini-bosses in La Tale, much to the dismay of lower-leveled players killing mooks on the same map.
The ghosts in Pac-Man also count as type 1 (at least in some versions), as they move randomly but chase the player if they see them.
Pac-man Ghost AI - The cool thing about the Pac-Man ghosts, and what it's rare for the clones to pull off (even if they go for deterministic rather than random ghost movement), is that each had a separate AI which, while all of them were simple, the result was that they made for a very effective team. http://www.atariage.com/forums/index.php?showtopic=68707 has some details, as it turns out.
Raikou, Entei, and Suicune from Pokémon Gold/Silver/Crystal. They are encountered like any other random Pokémon but the area they appear in changes. Unusually for this trope, the player is generally the one who tracks them down (and they have a habit of fleeing before you can catch them when they're encountered).
If Raikou/Entei/Suicune count, then Latios and Latias (from Ruby, Sapphire & Emerald), Mesprit and Cresselia (from Diamond & Pearl), and Articuno, Zapdos, and Moltres (only in Platinum) should also count.
They do. The games and manuals specifically call them "roaming Pokémon". Also from the remakes: Raikou, Entei or Suicune (whichever beats the one you chose at the start) in Fire Red & Leaf Green; and Raikou and Entei (but not Suicune anymore) and Latios or Latias in Heart Gold & Soul Silver.
The latest variation are Thundurus and Tornadus, who wander randomly through Unova, one in each version. They're less annoying than their predecessors, since they cause freak rainstorms on whatever map they happen to be inhabiting, and that tends to call attention to them, even from NPCs.
In Pokemon X and Y, after you beat the Elite Four, Articuno, Zapdos, or Moltres, depending on the starter you chose at the start of the game, starts roaming Kalos. (Choosing Chespin causes Articuno to appear, choosing Fennekin causes Zapdos to appear, and choosing Froakie causes Moltres to appear.) However, as soon as you encounter one of the legendary birds, after a few seconds, there is a close up on Articuno/Zapdos/Moltres, and then, it flees. It continues until encountered 10 times, where it will go to the Sea Spirit's Den, the location that happens to be the true spot that you can battle Articuno, Zapdos, or Moltres.
Deathguise / Death Gaze in Final Fantasy VI will spawn in a random area - can only be triggered by airship - once you hit the World of Ruin. The annoying parts about this being that it's invisible on the map and prone to running.
This is recreated with Ultima Weapon in Final Fantasy VII. You can at least chase him down, since he's visible on the world map.
Omega and Omega Mk. II from Final Fantasy V always roam the same room randomly. Not a problem when there's only one of them to run past —a definite problem in the Bonus Dungeon where an entire floor is filled with roaming Omegas.
In the Pirates of the Caribbean video game (spiritual successor to Sea Dogs) the Black Pearl would roam around the world map, and you could rarely find it as a kind of Easter Egg. Oddly, it doesn't become hostile unless you attack it.
Spore has the Epic creatures. These are extremely large versions of otherwise "normal" creatures from the game's library, and are particularly dangerous. They spend their time roaming around the map and killing wildlife, but will turn their attention to you if you get too close.
Earthbound Uses this system, and will even give players or enemies first attack if one "tags" the other from behind.
The Ultimate Chimera from Mother3 is an example of a Type 4. Appears in only two places (the second appearance is practically a Giant Space Flea from Nowhere example), and touching it is an instantGame Over. And if it sees you, it will chase you down.
The Spider Droid in the original Space Quest, and the security droids on board the Deltaur.
The Droid of Death in the starting area of Space Quest IV can either be a random or triggered encounter. If the wandering cyborg summons it, or if triggered by picking up the Unstable Ordnance after coming out of the sewers, there's no escape. Near the end of the game, there's the Imperial Probe Droid-style sentry bots.
The robots in Descent, particularly in the first game, start doing this a certain amount of time after the level starts. Especially dangerous if those enemies are Demonic Spiders, and the level has alot of intersecting passageways, such as the first game's 11th and 19th levels. Oh, and later levels come equipped with Mook Makers specifically for this purpose.
Twilight Heroes has both Types 1 and 2 - Type 1 in the Static Villains, who appear every so often but only in a specific area, and Type 2 in Wandering Villains, who may appear in any area (but at the same rate as the Static Villains). Both types are optional, and their appearance can be turned on or off by a choice adventure.
All the enemies in Left 4 Dead and Left 4 Dead 2 fit type 2 as the game's "director" AI will spawn them randomly throughout the levels. The Tank and the Witch are rarer, since you won't encounter them in every map, but you will encounter them at least once over the course of a campaign.
One campaign level in 2 specifically states that you will encounter numerous witches in that area. They're all wandering around as a Type 1 encounter, so you can avoid them if you see them first and know where they are.
In The Legend of Zelda: Phantom Hourglass there is a female pirate named Jolene who randomly appears on various maps as type 2 and patrols them as type 3. If she sees you have to escape or fight her off if she boards your boat.
There's this guy in Baldur's Gate that, if you look at the right (or wrong…) gravestone three times, summons a load of exploding dudes with swords to kill you. I don't think they ever turn up anywhere else.
In Super Paper Mario Trueform Mimi pops up in certain rooms of Chapter 2-4 if you dawdle too long picking an exit. She's frightening enough that it can cause you to rush through the level at breakneck speed.
From Final Fantasy VI, the Storm Dragon —it will fly out of its treasure chest the instant you open it, and fly circles within the cave until its speed and/or erratic pattern forces you into its path. Final Fantasy VI Advance also adds the Esper Leviathan, who lurks in the ocean between Figaro and Nikeah, and can only be encountered by taking a ferry between the two ports.
The Reaper from Persona 3, a Stalked by the Bell-type who will materialize in one of three spots (the staircase, your entry point, or the teleport back to the foyer) and then make a beeline for your party if you linger too long in a single floor of Tartarus. Particularly vicious in floors populated by nothing but the rare, elusive Gold Hand enemies.
The Grim Reaper in Alex Kidd in Miracle World appears if you step on a skull block, or is randomly triggered by ? blocks.
Nemesis is Types 2 and 4. There actually are times in the game where he will show up at complete random. Often if you keep going back and forth between the same areas, you'll soon hear the ominous "Staaaaaars..." come from the next room.
In Munchkin, one of the cards that can be played is called "Wandering Monster". It doesn't quite fit this trope exactly, as the monster is "wandered in" by a player.
This can be argued to be type 3, since it can be a literal type 3 if the player using the card is the one fighting (adding a creature to your own fight can earn you extra loot and levels). Even using it on one's opponents is a triggered event, just not triggered by the combatant.
Fallout 3 has all four types. Type 1 patrol certain areas of the Wasteland (e.g. Enclave squads and some Talon Company merc units), Type 2 are randomly triggered at certain points on the map (such as Sam Warrick the sniper or the crippled Deathclaw), and Type 3 takes the form of a scripted encounter with either Talon Company or Regulator squads, depending on the player's Karma Meter level, usually when quick-traveling. The Super Mutant Behemoths and some minibosses are Type 4.