Try the Street Fighter movies- not the seriesm, just the 2 movies.

Ninja Scroll- Movies +series,
Samurai Champloo- just came put 1 ep so far, but kicks major ass.
Full Metal Alchemist has it's share of action +fighting, and tons of story to boot.
The Bastard serires is short 6 eps and kinda hard to find, but great action.
Don't forget Beserk too.
Gokusen could qualify as a fighting show also, but mostly comedy.
Samurai Deeper Kyo is heavy on the fisticuffs too, and Scrapped Princess swings a sword or too, but it's not for everyone.
Shammanin Princess is pretty good on fights too, kinda reminded me of Yugi-Oh meets Kiki's delivery service on some really bad crack.

Thats about it off the top of my head.

PS: I've been lurking around the forum for a while, so I fugured it was about time to toss in my .02