Personally, I think the idea of "gateway bands" existing is stupid. I don't think their is honestly much of a disparity between so-called gateway bands and so-called non-gateway bands, much like popular vs underground metal groups. Those bands aren't necessarily more accessible, and it isn't necessary for a person new to metal to listen to them first. I'm the kind of person who actually listens to bands because I like them and see something worthwhile in them, so I don't have any reason not to like them years later. The idea of going through phases just seems a bit childish to me.
I got into extreme metal initally from Cradle of Filth, but my interest in metal grew stronger with bands who really weren't known at the time like Tvangeste, Fairytale Abuse and few others. I discovered those bands on my own from reading about them online, not from downloading or myspace - and being new to metal at the time, I had no idea which bands were popular and which weren't, not that that made any difference to me.
But agree with what was said earlier, the past few years or so more people are getting into metal from underground bands because of downloading, myspace, forums etc. Not to mention their desire to earn kvlt cred points plays a role, whether they admit it or not.