I'll start with a few "I don't think this applies" statements.
We have full 100% RPG in the custom maps, yea, sure.
But we also have Racing, Naval Simulators, First Person Shooters, Horror, Mini-games and many more.
Don't go custom to slap a genre on war3.
I don't think that "your decisions affects later gameplay/story" or "only one way to go" or "fixed story" or are a valid points for making something RPG or not.
There are many, many, many, MANY RPG games that don't have such thing.
e.g. have main quest, linear progression, maybe branching side quests, kill final boss.
At some point, somebody though "hmm, how about we make some little choice change story ?"
So, now the decisions you make change the outcome.
e.g. have main quest, have branching side quests, get to final boss, kill him or join him.
The former does not make a game non-RPG.
The point about FPS isn't 100% valid either, but even then, there are RPG games from FP perspective and there are also RPG games that the gameplay is FPS.
All that said;
I'd say that RPG is when there is a certain level of immersion within the characters, when you associate the game with the characters more than the game itself (not talking only named characters).
In war3, you are assuming the role of one of the named characters (talking campaign here) and his team, sometimes only 2-3 footmen, other times a whole army and few towns and act through a main quest with some side quests which enhance the experience or/and gameplay and/or character progression. The story is character-centered and immersive. Characters progress through the story, gaining new powers, abilities, skills and tactical diversity. e.g. Level-ups, abilities, items, units (yes, units, the characters are mostly army "generals" and the units they get are part of their tools)
I've never thought of war3 as RPG.
Strategy game with rpg elements? Yea sure.
The most story-driven Strategy game ever ? Yea. StarCraft 2 is a close competitor but I don't think that it has even a 1/10th of the lore of warcraft (whole franchise included for both)
But an RPG ? Mmmmm neh~ Strategy.
Anyway, in the end, I don't think that it really matters if you call war3 a Strategy, RPG, Strategy RPG.
regards
-Ned