As deep as that nut is sunk trying to get a good grip on it is going to be rough.

I agree cutting the bolt head is way to go. Get yourself some reinforced dremel cutoff discs - the black ones, not the garbage red ones. You should be able to slip the disc between the edge of the bolt head and the corner of the leg. Use fast speed on the dremel, but slow and steady pressure. Should help keep leg marring to minimum.

Once head is gone, hammer-punch the remains into the cabinet.

The cutting wheel might also help cut a slot into the inner nut as others have suggested.

Thinking to your earlier points, there was no reason to have the cabinet holes countersunk (counterbored?) for the brackets, unless they were supposed to be installed as shown in your "stolen" pictures. Shoving the nut into a hole only big enough for the bolt shaft would be a mighty task.

But as discussed and experienced, installing them the other way - with the nuts exposed to the air in the cabinet - is indisputably better. But if that were intended to be the case, there's no need for a wider hole in the wood to accept the nut.

So is this a case where, original brackets were just better back in the day and less apt to let the nut pull off the base to get stuck in the wood... or, just like Williams' infamous "oops" of assembling switches backwards in the same era, they installed the leg brackets "backwards" in a bunch of games too? I guess an air tool could pull the nuts into the wood to that counterbore without much difficulty after all...