By contrast, Paladins have always been more popular as tanks, but ended up being benched for a lot of Ulduar hard modes (as per GCs statements). Hence the need for a 2nd cooldown.
Paladins were very popular in Naxx remember (let's ignore Sarth 3d for now). Paladins have also always been a step ahead as far as threat is concerned. So really until Ulduar hard modes there's always been a lot of Paladin tanks.
The reason paladins started shining in T9 is that ToC introduced a brevy of bosses that stun you. Making cooldown tanking less useful and pure EH tanking more useful. Of course most people in a raid couldn't put their finger on why Paladins survived and Warriors didn't (it's not like you compare against a Druid and see gobs more hp after all).
Also, just looking at the stamina scaling talents, you can see that Paladin hp scaling would eventually outstrip the native higher base hp that warriors have. This was supposed to be balanced by ranged weapons for warrior tanks. Since the every ranged tank weapon since the shotgun has *less* stamina, it seems inevitable that Paladins are going to pass warriors in stamina, if not already. Although, it also seems possible that the shotgun had too much stamina to begin with (starting warriors farther ahead of paladins on the hp front).