The etymological dictionary of Dutch and Frisian names (dr. J. van der Schaar, Woordenboek van voornamen) mentions "Kei" (pronounced "Kai" in some dialects) and its variants "Kaei, Kaey, Kay, Key. Keije, Keijen" and says they are Frisian and are diminuatives (he calls them "vleivormen", so affective (positive) names, used in the speech of siblings, e.g.) and refers to names "Gerrit/Gerhard", "Nicolaas" and "Cornelis". So the author considers that these names could have derived from any of those traditional names. He offers no definite etymology beyond this. As Yellow Sky said in his answer, such forms are often quite far removed from the their original forms. The Danish name "Kaj" is mentioned under "Gaius". "Gaius" is not mentioned as the origin of "Kei", though. He does mention that maybe the Danish Kaj could have the same origin as the Frisian "Kei", but the Danish can certainly be derived from "Gaius" as well.
I think that if the name Kai is given nowadays, it's probably because people know the Danish name, which I think is more well-known than the traditional, but rare, "Kei"-forms at the beginning. This is just my impression, though.