No, there wasn't a time when Paladin was the best tank. There was a time when players weren't as well-geared and skilled as they are now, so Paladin was the safest tank because it largely relies on passive defenses. The way we play is an outgrowth of the game mechanics that have existed forever.

Also, there are plenty of jobs other than NIN being used right now for stuff. Thief and Dancer are competitive or superior for evasion. What would happen if they lost Utsusemi? It isn't like they're "I'm missing Ni but it's all okay!" better at evading stuff.

As far as the "I don't sub Ninja because I'm a gangster!" crowd. Well, outside of Abyssea to maintain that attitude you'd have to have tolerant and plentiful mages or a Dancer. I, personally, don't run with that many people anymore. I'd rather be on DNC/NIN with a BRD/WHM than change to WAR/SAM and bring a WHM/RDM to keep me alive. I do more damage, and it's less stressful on the mage.
Inside Abyssea, whatever. One good White Mage can heal pretty much any kind of party as long as you don't stick everyone in AoE range at once.