Heh, Tobal 2 is about to be released for Docomo cell phones here!
This is what I'd recommend. I'm big on fighters, so there's going to be a lot of those.
-Sengoku Basara 2: Capcom fucked up royally with their localized version of the original game, titled "Devil Kings" in the U.S. But the first game was crap anyway. Basara 2 is an amazing fusion of arcade style beat-em-ups and Koei's Samurai Warriors games. The stages are smaller and linear, but what makes up for this are the enemy variety and especially the over-the-top character designs and personalities. I HIGHLY recommend this if you like action games. It's been rereleased several times, so you should be able to get it cheap now. And if you like it, the expansion, Heroes, just came out last week, adding more characters and two player modes.
-Earth Defense Force 2: I prefer this over the 360 version. The frame rate may be (much) worse, but the game has two different playable characters and more weapons. It's cheap as hell, too.
-Melty Blood: PS2 port of the PC doujin game-turned arcade game, based on some light hentai-like PC game but changed around. *phew* All you need to know is that this is a fast-paced, combo HEAVY fighter that has virtually zero chance of ever seeing release outside Japan.
-Vampire Darkstalkers Collection: All the Vampire games in one package, with "hidden" bonus versions of Hunter 2, Savior, and Savior 2 featuring the entire cast, and one "new" character, the Demitri/Donovan hybrid Dee. I don't know why Capcom didn't release this in English.
-KOF Maximum Impact Regulation A: A more fine-tuned version of Maximum Impact 2 (AKA KOF 2006), with more characters and even better game play. In-depth thread is here:
http://www.evilbore.com/forum/index.php?topic=10975.0-The Rumblefish: Unique-looking 2D fighter (another ORIGINAL game) from Dimps. A sequel came out in 2005, but was arcade-only; this version has two characters from the sequel as unlockables, though.
-Twinkle Star Sprites: Polygonized version of the unique competitive shooter from ADK. Also contains the original Neo-Geo version.
-Arcana Heart: A brand-new fighting game series not based on any licensed property is rare. A 2D fighter is even rarer. This game was made by Samurai Shodown V and Special development staff; it's a one-on-one fighter in a more traditional vein, populated by a cast of various anime-cliche schoolgirls and settings. Despite this, the game play is fantastic and it feels much more solid and less combo heavy in comparison to Melty Blood. You can also choose different Arcanas for your character; these are basically MORE moves and abilities that can be added to any character, making for literally 11-12 versions of every character in the game.
-OZ: Beat-em-up game with some heavy juggling elements. I haven't played much of this, actually, but it seems cool. It's just that Sengoku Basara 2 pretty much kills everything else in the genre for me.
-Shin Gouketsuji Ichizoku: Bonnou Kaihou (Power Instinct Matrimelee upgrade): Quirky, bizarre fighter featuring Bobby Ologann as the new midboss. Brings back two older Power Instinct Characters, but drops the Rage Of The Dragon characters that were hidden in the Neo-Geo version. This game has the most bizarre soundtrack I've ever heard in a fighting game...it's all voiced and all WEIRD.
-Neo-Geo Online Collection Series: Some of these make it out in English, but good GERSTMANN are they slow to get them out. The best ports are Garou MOTW, Fatal Fury Battle Archives 2 (The Real Bouts), Savage Reign/Kizuna Encounter, and World Heroes Gorgeous. Avoid the Last Blade collection; it's a fucked up port.
NeoGeo Battle Coliseum is supposed to be hitting the U.S. soon, and Samurai Spirits Tenkaichi Kenkakuden is coming in the SS Collection whenever the hell that releases, so I'm removing them from the list. And YOU HAVE KOF XI, RIGHT? RIGHT??!

Let me check for more games when I get home. I know I'm leaving some stuff out.
I have Gunners Heaven, it's pretty good. I want Panzer Bandit, it's supposed to be another Guardian Heroes rip-off by Banpresto for PSX, and is supposed to be fun. I've never seen it for sale, tho.
Panzer Bandit is okay. It's made by Fill-In-Cafe, the makers of the Asuka 120% fighting game series, so the art and controls are very similar if you've played those games. Guardian Heroes spanks Panzer Bandit all over the fucking place, but it's still a good game. I never see it anywhere but I'm sure it must pop up in Akihabara from time to time. Another game I never see is Tecmo's Angel Eyes. I found it in Akihabara after looking to get it back for YEARS and quickly snapped it up.
I don't know how the PS2 version is but you might want to try out Beserk. I used to play the shit out of the DC one back in the day and the PS2 version seemed to be a step up from that.
[youtube=425,350]kg8hk3QrCBg&rel=1[/youtube]
Different developer, and the PS2 version is crap IMO.