I like using: NMoM.
It sounds like something exotic.
Neither NMoM nor not-MoM really rolls off the tongue and not being something doesn't look too good on box covers. 
Why not simply RoM - Return of Magic? It's not taken and all the old farts can recognise it as the return of... that... game.
If SD can pull it off in the spirit of MOM, I'll buy. Don't need to see the feature list or any screenshots.
Corrupted flying demon hounds from hell versus the ninja wrestling troll nuns. Ah, there was so much tinkering in that game, modifying the terrain (on strategical and tactical level), the units, their magical buffs, equipment... and the tactics.
Some games are replayable even nowadays. Magic Carpet 2, MOO2, Populous 2, Settlers, and of course... MoM. None of them ever had a worthy successor.