Ok, my memory of this game is very vague, but maybe someone will know.
When I was about 6 years old I went to England for a holiday with my parents, flying with Singapore Airlines. On the plane, they had Super Nintendos with a whole bunch of games, all of the games I can remember except one. They had Super Mario World, Tetris and Doctor Mario, Super BC Kid (AKA Super Bonk), Zelda: ALttP and the one which I don't know the name. It was a sidescrolling game and it had some guy in it shooting people in what I think I remember being a cave. There were bridges in it as well, but that's all I can remember. And no, it's not Super Metroid. Anybody know?