Except we did, because back then, the console command loop was part of the work done every frame - so your lookup still had to fit in the budget, or the player would see frames being skipped. Which, if memory serves me, happened as far as Quake 3.

Here's another important insight about how games were written back then: they were single-threaded. Rightfully or not, the cost of context switching was seen as too big, so everything was run in a single thread - maybe with an event loop (what kids these days call "async") thrown in for convenience, especially around UI. The games that did use threads, would use a small amount of them to offload some work that wasn't strictly frame-bound, or when outside main gameplay (e.g. in menu). I actually can't think of any game from that era, which would run multiple threads during main gameplay.

And sure, you can adapt the console with your linked list lookup to run on the event loop ("async"), so it would e.g. do a fixed number of search steps, then yield, and resume next frame. But the code for that would get much, much more complex than replacing a linked list with an array, even if you then also replaced linear scan with binary search.

So one other thing about games back then: things were much simpler, and skipping frames wasn't that big of a deal-breaker. Multiplayer wasn't so popular, there was nothing you could honestly call physics code - which would explode if you skipped frame without compensating, etc. And players were used to getting anything from 6 to 60 FPS, depending on hardware they owned. These days, a game console blocking main gameplay thread and causing frame skips, would be unthinkable.