This is a really old problem and a lot of research has been written on this.
There several ways to tackle it:
Reject PIE*kom > PGm *ga. However, as far as I can see, communis opinio is the opposite, cf. the following suggested cognates: Proto-Italic *kom (e.g. Latin perfectivizing co- and preposition cum), Proto-Celtic *kom, Slavic ** sъ-, and Hittite =kkan (encl. locatival sentence particle) ‘?’ Kloekhorst 2007 writes it was Sturtevant 1927 who first suggested this etymology. The reconstructed PIE form is * ḱom.
Reinterpret the conditioning factors of Verner's Law.
Phrase stress: Bennett 1972, Quinlin 1991, Hoptman 2002 (and also his 1989 dissertation). However, Tsimmerling 2007 finds this analysis irrefutable.
The low tone (in the initial pretonic position): Ivanov 1999 (and earlier). He suggests that "the Indo-European particle/adverbial element *kom could be used both as an enclitic or as a proclitic."
etc.
It seems no one is willing to abandon the ban on the Anlaut position though.
A couple of very important notes on Verner's law.
The interpretation you used in the OP - "voiceless fricatives, when immediately following an unstressed syllable" - has been abandoned in historical linguistic research and is considered untenable. The way it is interpreted now is that voiceless fricatives were voiced when they preceded a stressed syllable. This is a big difference!
Second, gone is the time of the notorious Neogrammarian motto "sound laws have no exceptions."
Finally, we don't really know for sure when Verner's law started to function (in Proto-Germanic? Before or after Grimm's law?) and how long it functioned. Also, there have been several attempts to merge Grimm's and Verner's laws into one.
The most importing thing to remember is that
"Any "sound law" is NOT simply an algebraic comparison of a protolanguage with a descendant, but a real sound change (or, in cases like GL, possibly a sequence of sound changes) that occurred in a real speaking population in real time" (Donald Ringe, p.c.)
It is also worth mentioning that a lot of Gothic preverbs (including ga-) have not been fully grammaticalized, could have been followed by other enclitics etc. See Arkadiev 2015: 209-210, Buscko 2008, Sizova 1978 and Sizova 2007 for further details.