Here's the thing...
Expressions that execute MEL commands (doing things like selecting objects and so on counts) are HIGHLY inefficient.
The reason that it doesn't work to substitute variables into object names when you're referring explicitly to their attributes in an expression is that those explicit references are evaluated by Maya when you make the expression to figure out to what nodes the expression node you're making needs to be connected. Use a variable and it can't figure that out when you make the expression.
Using "getAttr" and "setAttr" is a poor choice because those connections DO matter. If your expression affects nodes to which it isn't connected, Maya has to throw away everything it knows about the state of your scene and start from scratch on each frame because it can't necessarily determine what side-effects your expressions are going to have.
You must have some mechanism for making these objects, either a by-hand workflow or a MEL script. The approach that will make your scene evaluate fastest is to use a MEL script at object creation time to make an expression, probably one per object. This MEL script could either be triggered by a shelf button (if you're making these objects manually) or by the MEL script that makes the objects (if you're automating that part.)
You could, for example, construct the text of an expression to drive one object's visibility and use the expression command to hook it up at object creation time.
By not executing MEL commands in your expressions you'll avoid possibly costly re-evaluation of large parts of the dependency graph each time your scene gets recalculated, which will make your life much easier once these objects are in the scene.
Here's a specific example. Suppose you're making a hundred spheres in your scene with a MEL script and you want an expression that makes them oscillate in their local X axis.
You could make an expression (or even a scriptJob) that uses ls to get all the names of everything that has sphere in the name, then use getAttr and setAttr to make them oscillate. However, this would be SLOOOOOOOOOOOW. Also, you'd have some trouble getting the expression to evaluate because Maya uses its connections to figure out when to run it.
The better way is to use code like this WHEN YOU MAKE THE SPHERES:
string $mySphereName[] = sphere
;
string $myExp = ($mySphereName[0] + ".tx = sin(time);");
expression -s $myExp;
(Note that sphere returns an array of strings which contains the name of the transform node in element 0 and the name of the shape node in element 1.)
This makes a separate expression for each sphere that's connected to its tx attribute. Maya now knows when each one needs to be evaluated by virtue of its connections, and the expression itself doesn't use any MEL commands that create or destroy nodes or get or set their attributes.
-- Mark