The New Zealand Story
The Kiwi that shoots arrows..
http://www.mamedb.com/game/tnzs
Avenging Spirit
A unique platformer as you play as a ghost trying to process an NPC to become playable and clear the level.
http://www.mamedb.com/game/avspirit
Willow
Platformer that has some interesting TAS ideas. Easy mode starts off with a higher level Magic Meter (able to use powerful spells sooner) but Hardest is the opposite, starting off with weak spells.
Rodland
http://www.mamedb.com/game/rodland
Slightly reminds me of Snow Bros that you need to defeat all of the enemies to advance.
Psychic 5
http://www.mamedb.com/game/psychic5
Really unusual platformer, you get to play as 5 different characters with strengths and weaknesses. One guy is tall and jumps very high while one girl is small but can hover effectively in the early game.
Bionic Commando. The Arcade version is a completely different game when comparing to the NES version.
Mini edit: Seems like Mukki has produced one and it is currently in the Workbench
http://tasvideos.org/forum/viewtopic.php?t=10020
Toryumon
http://www.mamedb.com/game/toryumon
Despite the 'mon' at the end, it has no relation to any Japanese monster franchise what so ever, it's a puzzle game where you need to arrange the falling blocks to form circles. The bigger the combo, the better the outcome. I remember playing this against the AI on the last stage and it was impossible... non-human like.
Chimera Beast:
http://www.mamedb.com/game/chimerab
According to the database there was only the prototype version, as far as I know it's fully playable during the early noughties. It's a unique SHMUP that you powerup by eating other enemies. The different type of enemy will change the player's physical appearance and weaponry.
Blazer
http://www.mamedb.com/game/blazer
FlashGal:
http://www.mamedb.com/game/flashgal
It's an autoscroller unfortunately, but the girl you play as looks very similar to Blaze from the Streets of Rage trilogy.
Mega Twins:
http://www.mamedb.com/category/Platform?start=300
I couldn't remember much of this Capcom Platformer, probably has some TAS potential.
Quartet:
http://www.mamedb.com/game/quartet
4 Player Co-op and one of the background tracks contains "Se-Se-Sega..... oh yeah, oh yeah, oh yeah".
Congo Bongo (aka Tip Top):
http://www.mamedb.com/game/congo
Sega's attempt into making Donkey Kong but with isometric graphics.
Heavy Metal
http://www.mamedb.com/game/hvymetal
An autoscroller but has an interesting secondary weapon. You can hold the button to aim where the missile is going to land and you can aim at a target pretty far away.
I'll post some more soon if I get to remember most of the other arcade games I used to have on MAME back in the early noughties.