Foreboding is a difficult emotion to evoke, but amplifies the enjoyment of having wandering monsters in adventure games. This is a procedure for using them in old school D&D. I used a variant of this procedure in Emern, but this is the cleaned up version.
Example of a wandering monster table using monsters from Necrocarcerus.
You will need
A wandering monster table organised into rows and columns as above.
A blank table with the same number of rows and columns as above.
3d6, with one die distinct from the other two.
Designate one PC as "the guard" or "on watch" who will roll. Whenever a random encounter is rolled for, they pick up the 3d6 and roll it. The distinct die determines the column, telling you what they encounter, while the other 2d6 tell you which monster it comes from. The guard should fill out the grid as entries are rolled.
Each of the top six columns has a different effect:
1 - Monster - The party encounters the monster(s). Roll surprise and opening distance.
2 - Lair - The party discovers a lair of monsters. Roll surprise and opening distance. If the PCs surprise the monsters and the monsters do not surprise the PCs, the lair is empty.
3 - Spoor - Monsters are nearby. -3 on the distinct die's next roll (count rolls less than 1 as 1).
4 - Tracks - The monster has passed this way recently. Characters who can track can follow this to hunt the monster. If they choose too, roll the distinct die and subtract 2 from its result (count rolls less than 1 as 1). Or, characters may choose to divert away from the tracks and add 2 to their next roll of the distinct die.
5 - Traces - Traces can be used to identify monsters.
6 - Traces - Traces can be used to identify monsters.
Notes on Designing Tables
These are regional tables, obviously, and you can certainly have more than 11 entries organised around a bell curve. The important part of this method is really the columns and the possibility of more than a binary outcome for the roll.
This does mean that just under 33% of all random encounter rolls will result in the possibility of encounter a monster. If you wish to reduce this, switch to a d8 or d10 and add more Spoor, Track and Trace columns.
Each monster should have two distinct traces. Repetition is fine, but whenever possible, repeat the entries in different columns rather than the same column, unless the purpose is to confound the PCs. If your game has a skill governing knowledge of monsters, consider allowing the PCs to roll it to identify some possible candidate monsters who would leave these traces. If you don't play with such a skill, consider making the traces such that together, they provide a relatively clear and narrow list of candidates. When I used this in Emern, one of the entries was giant shock lizards, so the PCs encountered lizard scales and clawprints all over the place, with the shock power remaining a surprise to be discovered in the actual encounter.
The main purpose of tracks is to help the PCs determine where the monster is without seeing them directly. Footprints on the ground or crushed vegetation are classics, but I also like to use distant recurring sounds. I like to salt the tracks entries with a few blanks or "None" entries for monsters that are untrackable, which creates foreboding. However, I would encourage you not to simply make every incorporeal, flying, etc. monster untrackable. The Flying Oozes leave chemtrails from their jetpacks, for example.
If you increase the number of columns, consider secretly rolling 1d6 whenever tracks are rolled. 1-3, the PCs mistake the direction the tracks are going, and when they think they are veering away, they are actually closing in on the monster, and vice versa.
My favourite kinds of spoor are abandoned lairs, camps, prey or victims. I normally count spoor as relatively fresh, but you may wish to roll 1d6, with 1-3 meaning it is fresh (and therefore provides -1 to the next roll), and 4-6 meaning it is old (+1 to the next roll). Spoor is also a good entry if you want to introduce clues or other details about the world or story, since it is a trace of the monster stopping for a brief period. Spoor can also involve minor trap / non-combat encounters - the table above has the Mendicant Parasites leaving gibbering madmen in their wake who the PCs can try to interrogate.
Lairs should not automatically result in encounters, but they should require immediate action or decision to avoid having an encounter, whether to seek cover, run away, etc. if the PCs don't want to fight or clear it. Use the No. in Lair entry to determine how many monsters should be encountered. This is also where most monsters will store their treasure, as opposed to sitting in the purses or stomachs of monsters randomly wandering around.
Depending on the monster, I sometimes allow PCs who destroy or eliminate the lair to remove or blank the entry on the wandering monster table, allowing them to partially clear the area. Future rolls of that entry do not produce random encounters. This creates a different feel between monsters who are singular, recurrent entries (there is only one Pustulent Dragon in the region) or precarious invaders, and ones who are swarms or hordes or endemic to the area.
The actual monster, obviously.