Zaratustra made this topic back at Pyoko where he asked everybody what they liked and didn't like about Cave Story, and if it still existed I could point to it and show you where I explained why Cave Story isn't a metroidvania and in fact why the metroidvania formula sucks. But it's gone so I have to recap here instead.
The basic metroidvania approach is to take the sequential progression of stages and levels of Super Mario Brothers, cut it up into bits of varying lengths, and then hold it all together in hopes that it will coagulate into some sort of tumorous ball of interconnected randomness. (You may have detected from my word-choice that I don't think very much of this design--and you'd be right!)
The apparent appeal of the metroidvania is twofold (other than the fact that it's really easy to do); first, it makes implementing something I'll call the "first law of Miyamoto" straightforward; second, it gives your game much more "organic" "structure". Both of these principles are on shining display in the single most prolific metroidvania-style game series to date: The Legend of Zelda.
The "first law of Miyamoto" is something I read about around the time Wind Waker was coming out. Someone (and I'm only assuming it was Miyamoto, here) said it was always important to show the player something he couldn't do yet as early as possible; it made the player look forward to the acquisition of the lacking ability more. It's supposed to give you a feeling of satisfaction when you finally find the key to that particular lock. In practice, you're constantly butting up against the limits of your own abilities; you see treasures and mysteries and you're reminded that you are inferior. The pleasure of the first law is the same as the pleasure of hitting yourself with a hammer--because it feels so much better when you stop.
The second reason metroidvanias keep popping up is because of the more "organic structure". The idea goes roughly that, since a videogame is a model of space, the space is more realistic when the areas are contiguous, connected at multiple points. A real place has width as well as depth as well as breadth, so the player should be forced to travel in as many dimensions as the game will allow: east as well as north, in as well as up. This is a wonderful realization, and its only flaw is that this interconnected, nonlinear gameworld is married to a sequential, linear game design. The only locked doors that you will not pass through are optional cul-de-sacs containing unnecessary plunder; the only bosses that you will not fight are end-game bonuses hidden in the outskirts of the world. The hideous offspring of this mismatched marriage is the devil-demon Back-tracking.
Cave Story is not a metroidvania. It does not make a habit of showing you treasures you don't yet have the ability to acquire. It does not make you backtrack every time you want to move forward. It does contain a hub, but almost every area accessible from the hub is connected to the same spot. It does force you to revisit an earlier level (twice!), but (in each time!) that level is so transformed between visits that it qualifies as a new location, while still retaining the emotional weight of recognition. It is all the better for these qualities.