OH NO! You're NOT supposed to have the CLAW at the start of the game. I checked the code and an override was in place. If it wasn't for your play-through video I would have missed that. ... How...?
There are two places to go; one is the big room beside where you start the game; you need the Jump Boots to cross the Spike Caverns (Change in music) and get the claw (Which you already got). The next is to head down after you cross the mid-point in the first world to reach the fire caves (It's the vertical room with the save point; you need to bomb the floor on the left side -- easiest spot to do it is when you enter the room). Most of the remaining upgrades you need to reach the top pillars of the first large room are down there. When you get down there (first) head east and circle around to get the RED CAPE so you can resist heat damage. After that, you can head down either path and enter the Hot Zone to get the MAGIC FEATHER.