I avoid random names (and most tables for that matter) for a very specific reason, if it doesn't move the story forward - it doesn't deserve a name.
I am all for my players deciding to visit the random shop, talking to the random guard, playing dice with the bar patron, etc. But, I generally do not give them the name. It is an easy, non-spoken context clue that, while you may have fun or get something you need, it is not pushing the main storyline forward.
For example, most of my cities, I have the owners and families and history and décor and services available for at least one of each kind of shop needed: apothecaries, stables, inns, taverns, smithies, tailors, churches, etc... If the players need more than that, then they can explore, but there needs to be an upfront set piece that says, this person is not important unless you want to play dice or chat about the weather. I find this gives the storyline more fluidity, as opposed to an entire session that is devoted to finding the cheapest chainmail or listening to a conversation between an old married couple.
But I know this is just my take on it, and have had a great time being a player when DMs use random tables. There is no correct way, just a better way for me personally to DM.