The only "underground" spot I'm aware of is in Yokohama. Muthos is something of a Bemani (Konami's music game series) mecca, or at least it was. I"m sure many other "scenes" have similar havens.
As for places I liked, check out Club Sega Akihabara. It's like 5 floors of games. Not a ton of Bemani, though. There was also a HUGE place near Hiroshima station on the top floor of some mall building. Basically, just walk around. Video arcades tend to be on the upper floor of pachinko parlors. Almost everything runs on cash, so you won't have to worry about having tokens laying around you can't use. Have plenty of 100yen and 50yen coins. Most places have change machines, of course.
I was mostly watching out for the Bemani games, but most places you'll find have huge rows of candies with all sorts of stuff. When I visited (2005-ish), there were some collectable card based video games that were very popular.
While you're in Akihabara (and I assume you'll visit the area), you should check out G Front. They sell all kinds of arcade game parts. Take the Ginza line (orange, IIRC) to the Suehirocho stop. Come up out of the stop and look around the street corner. The signs were very obvious when I was there. I don't remember which corner it was on. This assumes it's still there, of course.