I played the Wii VC version again about a week ago for the heck of it. Surprisingly, it wasn't as difficult as I thought I remembered it being; 4-4, 5-4, 8-1 and 8-4 were the only levels that cost me more than three lives (though I got incredibly lucky on 7-4). Then I played it again as Luigi. I can't believe I ever thought his superior jumping was worth the loss in acceleration and traction; I lost twenty-plus lives on 8-4 alone due to his inability to do those backwards cliff-jumps properly.
But yeah, memorization is pretty much required to get decent at the game. Even still, I find the original version somewhat reliant on luck; due to sprite limits, there's several places where you have to be wary of the potential of missing/reappearing enemies.