Is it possible to create lookups on temporary symbols that still allow the symbols to be automatically removed?

Here's an example of how you can use ExpressionStore for this:

tempCache = Language`NewExpressionStore["ilmbiahi"];

bindTempSyms[holder_Symbol, key_, syms_] :=
  tempCache@"put"[holder, key, syms];
getTempSyms[holder_Symbol, key_] :=
  tempCache@"get"[holder, key];

Module[{list},

 Module[{sym1, sym2, sym3},
  bindTempSyms[list, 1, {Hold[sym1], Hold[sym2], Hold[sym3]}];
  sym1 = "dog";
  sym2 = "cat";
  sym3 = "my shattered hopes and dreams";
  ];

 getTempSyms[list, 1][[-1]] // ReleaseHold
 ]

"my shattered hopes and dreams"

Names["sym*"]

{"sym1", "sym1$", "sym2", "sym2$", "sym3", "sym3$", "syms"}

Note that the Module-ized versions of these symbols don't appear.

What's nice about this is whenever list went out of scope—even if it were returned from the Module (and if list wouldn't have been bound to Out)—those bound symbols would go out of scope too.

On the other hand, you indicate that your biggest issue now is in display? I'm not sure exactly what you mean there, but there are many ways to display big values compactly. The standard way is through BoxForm`ArrangeSummaryBox. I won't get into how it works, but there are many, many usages of it across the site. Here's how it can work with a general data structure as implemented here:

RegisterDataStructure[
  pkg`myObj,
  pkg`myObj[Hold[sym_Symbol]]
  ];
pkg`myObj[] := Module[{tmp}, pkg`myObj@Hold[tmp]]

po = pkg`myObj[]

Here's how you could set the data on such an object:

pkg`setObjData[po, RandomReal[{}, {100, 100}]]

Note that the object data has changed:

pkg`myObj`Data@po // ReleaseHold // ByteCount

80152

This can be chained with ExpressionStore to make some very powerful encapsulation strategies.

You could use strings containing the (full) symbol names as keys. This function may come in handy:

f = Function[s,
   Context[s] <> SymbolName[Unevaluated[s]],
   HoldFirst
   ];

Examples:

a = 1;
bla`a = 2;
bla`bli`blubb`a = 2;
f[a]
f[bla`a]
f[bla`bli`blubb`a]

"Global`a"

"bla`a"

"bla`bli`blubb`a"

If it is OK to use OwnValues and you avoid them just to prevent large expressions from appearing as output, then you can wrap the temporary symbols you create in Hold and release it when necessary.

For example,

$HistoryLength = 0;
Names["temp*"]
(*{}*)

sym = Module[
 {temp},
 temp = 1;
 Hold[temp]
]

Names["temp*"]
(*{"temp", "temp$2465"}*)

sym =.
Names["temp*"]
(*{temp}*)

EDIT

By the way, I have once faced myself a task of garbage collecting Temporary symbols with DownValues. Unfortunately, I don't have time to write a full solution at the moment, but the main idea is simple: you introduce an auxiliary Temporary symbol to count references to your main symbol (which now can be not Temporary):

ClearAll[reference, new]
new[] := Module[
  {ref, store},
  reference[store] ^= Context[ref] <> SymbolName[ref];
  reference[ref, store]
]

Now you can attach any definitions to the generated store$123 symbol and use reference[ref$123, store$123] objects in your code to access them. If no reference[ref$123, store$123] objects are referenced any more, then ref$123 will be released, which you can check with Names@reference@store$123. Of course, this approach would require to call garbage collection manually from time to time, but the benefit of calling garbage collection this way is that you can implement a finilizer which will be executed before releasing store$123 symbol.