As @Paul & @PolyGeo suggested, I think trying to make this a Python Add-in makes the most sense, and I will pursue that idea later.
In the meantime, I put together code that will Add/Update the TOC Name of user-defined layers in an MXD with feature counts. For my purposes, I just created this as a GP tool that would accept individual layers via a multivalue input that accepts "Layers" in the script tool. That allows me to update multiple layers "on-demand", just updating the feature counts of those layers of interest.
I haven't come up with a way to have this run automatically, however in doing some testing of old MXD's, that may not even be desirable. If you have a lot of layers with a lot of features, it could be a slow process.
import arcpy
LayerInput = arcpy.GetParameterAsText(0)
mxd = arcpy.mapping.MapDocument("CURRENT")
for lyr in arcpy.mapping.ListLayers(mxd):
#Skip over group layers, as they have no values to count
if lyr.isGroupLayer:
continue
#Determine basename of the layer, without the feature count
name = str(lyr.name)
#Determine if the layer is in the user-defined list
if name not in LayerInput:
continue
#Determine if the layer name already includes a COUNT
if "[" in name and "]" in name:
lpos = name.find("[")
basename = name[:lpos-1]
else:
basename = name
print " Updating feature count in TOC name for layer: " + str(basename)
arcpy.AddMessage(" Updating feature count in TOC name for layer: " + str(basename) )
# In 10.1, you may be able to use arcpy.da.SearchCursor to increase the speed.
#http://gis.stackexchange.com/questions/30140/fastest-way-to-count-the-number-of-features-in-a-feature-class
#fcount = 0
#cursor = arcpy.SearchCursor(lyr)
#for row in cursor:
# fcount += 1
#del cursor
#Get the feature count
fcount = int(arcpy.GetCount_management(lyr).getOutput(0))
#Update the lyr.name property
lyr.name = basename + " [n=" + str(fcount) + "]"
del fcount
arcpy.RefreshTOC()
#Garbage collection
del mxd