OK. How about this.
If we ripped out the entire storyline of Fire Emblem, and replaced all the character graphics with abstract shapes, would it still be a RPG, or would it become a wargame?
Did Tunnels of Doom have a story? I don't recall if there's any specific reason why you're generating the random dungeons.
Do RPGs not need an in-game story? Unless Tunnels of Doom lacks one, I can't think of any which lack one entirely, perhaps Aklabeth (sp) or maybe Telengard.
I think you're right, though. The storyline requirement is meaningless. In the olden days there wasn't enough memory for a story, and in modern times there's enough memory for anything to have an in-game story.