@Mr.Wizard I also said I learned a lot investigating these examples. The most important thing I learned is simpler than all this, so you may have seen it, but if not, it is probably nice to compare the following
Trace[{1, 2, 3}, TraceOriginal -> True]
-> {1, 2, 3}
Trace[{1, 2, oki}, TraceOriginal -> True]
-> {{1,2,oki},{List},{1},{2},{oki},{1,2,oki}}
With[
{expr = {1, 2, oki}},
Trace[expr, TraceOriginal -> True]
]
-> {{1,2,oki}}
Mathematica truly remembers what has been evaluated :). Also it does not go through expressions consisting only of basic types like List and Integer.