At this point, there is no final, airtight answer to the question of whether the /na/ in /kaNnazuki/ and /minazuki/ is related to /nai/ ("nothing", "no ~") or /no/ (genitive particle) because the matter has not been settled definitively.
We can say that the "genitive particle" explanation (giving "month of water" and "month of gods", rather than "... of no water/gods") is preferred by the majority of contemporary specialists in Japanese historical linguistics. The "... of no water/gods" interpretation is generally rejected as folk etymology, and the same genitive /na/ is argued to be visible in other words, such as:
- minato "harbor" = /mi/ "water" (cf modern /mizu/) + /na/ + /to/ "door"
- nunato "sound of jewels" = /nu/ "jewel" + /na/ + /oto/ "sound"
(Normalizing OJ morae to NJ equivalents because details not important here)
... But there are also modern linguists who disagree with this analysis. For example, in Alexander Vovin's Descriptive and Comparative Grammar of Western Old Japanese, the /na/ in the above words is analyzed as a plural marker:
18.104.22.168.4 Plural marker -na
There is another plural marker -na in Western Old Japanese that is not productive: it survives predominantly in compounds. Traditional Japanese analysis defines it as a genitive marker in some cases [...] and as a locative suffix in other cases [...], but a closer examination reveals that it has nothing to do with either the genitive or the locative. This plural marker also survives in modern compounds like ta-na-gokoro "palm of the hand(s)," mi-na-giwa "water front," ma-na-ko "pupil of the eye," etc. From the examples below it becomes clear that -na follows stems of nouns designating paired body parts [...] uncountable nouns [...] and two temporal nouns [...]. Such usage seems to be in perfect agreement with the above proposal that -na represents a relic plural marker.
... And so, Vovin believes that /minato/ means "waters' door" and /nunato/ means "jewels' sound", with the /na/ indicating plurality rather than a genitive relationship. Now, you don't have to believe that Vovin is correct. (I don't, for reasons that are complicated and not relevant here.) But the fact that he is able to mount a reasonable argument for his viewpoint indicates the thinness of the evidence we have for how the construction arose: multiple non-crazy theories can explain what we see in the historical record.
(Incidentally, don't know if Vovin has ever voiced an opinion on /kaNnazuki/ and /minazuki/ but based on his other writings my guess is that he would probably go with "month of the gods (pl)" and "month of waters (pl)", seeing traces of genitive /no/ in the voicing of /tuki/ rather than in the /na/.)
There are also other theories, e.g. the argument that the /kaNna/ is related to /kaminari/ "thunder" and so on. These are minority viewpoints too.
So, the summary:
- Most modern historical linguists believe that this is a genitive /na/ and the words mean "month of water" and "month of gods". It is probably safe to call this the current scientific consensus. This doesn't mean that it has been proven correct -- just that most scientists (linguists) in the field consider it the most likely (or least unlikely) explanation.
- Many older sources, and indeed the standard kanji used to write the words, support the opposite interpretation, "month of no water", "month of no gods". There are even communities who have built up traditions around this interpretation, like Shimane prefecture. This is why there are plenty of sources who argue for this interpretation, even today.
- The actual construction is very old, predating the first written Old Japanese, and so there is no evidence showing its evolution. Thus, it is possible that both of the theories above are incorrect, and an entirely different explanation like Vovin's is the right one.