In that old submission discussion there should also be a link to a new version by me of the first level only, 13 seconds faster.
I was also thinking of doing this game but still haven't gotten around to it...
I'll give comments on your attempt later.
Edit with comments:
1st: watching the speedrun on SDA of this game is of course mandatory for anyone making a run.
http://speeddemosarchive.com/Shinobi3.html
All the following comments apply to your first version:
You should never have to turn back to avoid the shuriken flying after you in the beginning if you kill the right ninjas.
After the climbing section, don't do a double jump. You can gain downward momentum faster with the jump kick. It also looks like you lose some forward speed.
You can pick up more shuriken along the way, without losing any time, so you wont have to stop to do a jumpkick on the last enemy before the boss.
The chasm before the boss can be done faster.
You can jumpkick off people and land on the ground at the same time, no recoil. You can see this in the first level i posted.
Do some testing on if it's faster/slower/equally fast to land from a regular jump, a double jump, and a jumpkick. Then use that info to choose the fastest possible variant in every case.
You missed an extra life in the horse level. That is a very bad idea since the mijin jutsu is silly powerful and you want to use it on the bosses whenever you can. Also you can probably do something more interesting than standing to the right all the time.
Level 2 boss: use 1 shuriken + jutsu and he'll go down directly.
When dropping down a floor in level 3, use the jumpkick do go faster.
Don't run in the wrong direction on conveyor belts. Jump.
I'm not sure if it's faster to go up on the right or the left in the conveyor belt area with the sparks. Both are possible. Test.
Very good agression on the brain (?) jars.
Jumpkick in the beginning of the underground area. There are some other slow spots here which I think can be avoided.
I suspect that the jutsu is beneficial on the level 3 boss too, but I'm not sure.
Good luck with it. Don't feel disencouraged because of all the criticism, it's there to help you.