At first sight, one might recognize 是非 from expressions such as zehi goraikan kudasai (We very much hope you will honor us with a visit.) and identify the word zehi with an affirmative, eg certainly.
Then zehi mo nai would be very strange to that person, as it would sound to him like 確かでもない and appear to mean the opposite of what it really does.
However, zehi in that meaning is already a derivation from its original meaning, which is evident when we look at how it is written with Chinese characters. Note that we are talking about a sino-Japanese word for the first time, so taking a look at the kanji is a good thing.
The two characters 是 非 literally mean existence and non-existence, or rephrased, yes or no. Thus zehi mo nai in turn literally expresses [It is] not even [a question of] yes or no., ie there can be not doubt, it is inevitable.