First, we must understand a fundamental: Technology has improved and miniaturized a great deal since the arcade machines of the 70's and 80's. The smartphones that we hold in our hands today are more powerful than some of the best supercomputers of that era.
While arcade tables and their innards may vary depending on the company that produced them (and the exact year of production), I'll be looking specifically at one called "Space Zap", as I found a blog where someone opened up an old unit.
The first thing that modern arcade tables have over their classic counterparts are the monitors. The classics use CRT displays (if they were old enough, they were the kind that used replaceable vacuum tubes) which were bulky, and would take up quite a bit of room behind the display.
Next, let's look at the CPU of this Space Zap unit. The blog says it's a Z80 chip, the same sort that powered the Tandy/RadioShack TRS-80. It runs at about 1.77MHz. There are also two ram boards at 8KB each (for a total of 16) There is also a board that contains the game, that is the same dimensions as the CPU board. This board contains roughly 12KB of data (might be a little more, was looking at the file size of the ZIP'd MAME ROM file)
Those main boards are sandwiched together in a case that looks roughly the size of a 2-slice toaster. With the panel that deals with counting coins (and the box below for collecting them), the wires to connect everything and supply power, and leaving enough room for venting so the whole thing doesn't overheat. There's not too much room left.
By comparison, a modern-built cocktail arcade can use an LCD display that could be no more than an inch-and-a-half thick (or less) freeing up all that room underneath.
And underneath, you don't need all that much room! You could probably fit any modern PC in there; with hard-drive, video card, and everything. You'd probably be able to run the latest AAA games on it. But if all you're running is a an emulator, you need very little more than a Raspberry Pi which has at least 395 times the processing power (700MHz - 1.2GHz), and at least 16-thousand times the RAM (256MB - 1GB) of our starting Space Zap table. All in a package that is under 3.5in by 2.5in.
To store all 5000 game ROMs, you'd just need to connect a MicroSD card. even if we go with a cheap 16GB card, at 5000 games, that gives us 3.2MB per game. That's over 200 times the space our Space Zap game needs (granted, depending on the eras included in the collection, not all are going to be as small as this game).
(NOTE: I am not saying the machines you are looking into are using the setup I propose here. I am just offering comparison to illustrate just how much the underlying technology has evolved. What used to be stored on a board around the size of a DVD case, now fits into a tiny fraction of a chip that's about the size of a dime.)