I used to play this game a lot on the SNES about 9 years ago, I beat it a few times and even got up to 80 lives once (there's many 1ups and 2ups if you look around enough, to make up for the fact you can die so easily, but I also once got to Chapter 7 without dying). I never went for pure speed back then, but I know for sure I'd have gotten nowhere close to 16 minutes if I tried ... running fast is too risky, and each death wastes a signifiant amount of time.
The insane amount of obstacles causing slowdowns is exactly why choosing the best path can make a big difference ...
I took a look at Bubsy 2 recently, it's even faster (fast acceleration, less slowdown) but also much weirder and the controls are different ... I'm sure it'd also make an interesting run, though, and I made a
1 level run for now.