The idea of giving monsters identifying traits is a good one, but the implementation needs to differ from monster to monster.
For a creature like a beholder or a gelatinous cube, you are rarely going to meet more than one at a time. So, the identifying trait is more about "how is this monster unique" than "how do I tell beholder #1 from beholder #14." (If you typically run encounters with 14+ beholders, you're playing D&D very differently from how I play...)
For unique individuals, a little implied backstory or some unique abilities can be pretty cool. It's also less likely that a DM would ever roll on a table. Rather, it's more about picking the flavor that best matches the existing situation. Also, these monsters don't show up that often, so you don't need more than a few suggestions. 3-5 suggestions would be more than enough for most DMs.
For a creature like an orc, the objective is the one originally noted - telling the orcs apart. Here, a table of 12 entries isn't actually all that useful because a campaign could involve fighting hundreds of orcs and it would be really odd to have dozens each with a missing eye. Of course you could explain that by giving the tribe an eyepatch fettish, but then your random table is more or less going off the reservation adding weird details to your game world.
For humanoids, what you want is a software tool that prepares an encounter sheet with the monster stat block and a listing of individuals with their identifying traits and a place to track hp. That tool is going to want a much longer (and well weighted) list of characteristics and the ability to modify that list depending on the type of humanoid. I would probably want to adjust the trait table based on characteristics like (1) the environment the humanoids (or humans!) live in, (2) the race of the humanoids and maybe (3) the savageness of this particular tribe. You might also include on/off settings like whether the tribe is particularly religious, militeristic, superstitious, cult-like or whatever.
-KS