There seems to be a general assumption by many that the internet was predestined to win out over these other pre-existing nets.
...
If the existing services that were taking off when the internet came along from behind had gotten their acts together - and gotten for example inter-provider mail working, the internet in its present form may not have happened.
Certainly not predestined, but economic forces at some point would have demanded interoperability. Whether that meant a true "network of networks" (as you say, and as the internet was defined as), at some point a common-denominator protocol,service,etc would be required. The rise of cheaper and faster electronics (and therefore communications) would make any other scenario unlikely (barring dumb government regulation or something).
It may not have looked been TCP/IP, but it would be an Internet Protocol nonetheless.