[MENTION=6788973]MostlyDm[/MENTION] Always a good topic to discuss

I think you hit the nail on the head that there are different reasons for using random encounters and thus the "just rightness" of an encounter table (or whatever your selection method is) depends on how well it meets your goals.
I'll illustrate this with 4 quick examples with pictures. To be clear, I don't think an encounter table has to fit just
one of these molds; it's perfectly possible and consistent for a DM to run random encounters that have multiple goals ranging from resource attrition, to deadly challenges, to roleplaying dilemmas, to enhancing the flavor of an area, and everything in between.
1. Persistent threat
My example here is from my 4e conversion of the mega-adventure
Dragon Mountain. While my version has a lot of "new school" design to it, this is the classic way encounter tables have been used: if the PCs take a long time or explore off the map or draw attention to themselves, then they have an encounter that causes attrition of their resources. I just took that essential idea and made it a bit more interesting.
http://i.*****.com/bs22cTq.png
2. Escalating threat
A twist on #1, this example is from my 5e adventure
The Beast of Graenseskov. The idea behind it is that you start off with a low die (e.g. d4), and then as various events/PC actions escalate the threat level in the region you incrementally increases that die to d8, d10, d12, etc.
http://i.*****.com/eQnWylZ.png
3. Megadungeon simulation
This one comes from an Underdark game I was DMing and was a collaboration with some of the other players who are also DMs. I'll post two snapshots of the master table below, but you're better off looking at our
crazy spreadsheet on icloud to understand how massive this is. The objective here is that, yeah, there may be some story, but the main activity of the PCs is exploring how they want, where they want; thus the DM would rely heavily on encounter tables to drive the action.
http://i.*****.com/cSJKnHV.png
http://i.*****.com/4VNgECh.png
4. Story/Adventure-themed tables
Lastly, my example here is from an adventure I currently have in the works called
Shadow of the Faceless God. Like your second example in the OP of a table with named NPCs and specific references to elements of that particular adventure, I think this approach is probably best for published modules. Why? Because the author/designer has a better grasp of the module initially than the DM, so these tables are almost a written long-form of what a DM would improvise in his or her own game.
http://i.*****.com/95jPjyv.png