Strictly speaking you’re correct about it not originating from lolcats. It’s origins were lolspeak which was little known when it first started.
But along with “teh” and “pwned”, “kitteh” definitely made it’s first written appearance informally as part of lolspeak way way before 2004.
And then lolspeak begat it’s own branch which became lolcats.
If you follow their spelling “rules” (which they have created) kitteh follows a similar pattern to “teh” (an almost universal typo of “the”) which morphed into the acceptance of teh as part of their own language meme, limited, at first, just to those in the know but eventually making it’s way into the mainstream.
This type of stuff along with L77tspeak (leetspeak) was a type of shorthand or code for the early tech savvy denizens of the Internet. You can still see it in screennames even nowadays. If someone asked about any of these terms, that was their way of identifying the noobs, sometimes not with kind intentions.
Nowadays, with the widespread use of computers and Q&A sites, pretty much anyone with an Internet connection can figure it out.
Even 4chan has garnered articles in the MSM so not much is secret anymore. Even txtspeak is creeping into everything ~
So, ironically, the best response is to revert to standard grammar and spelling usage which so many young people (the schools being as lax as they generally are) can not remember how to properly decode. And the beat goes on…...
:D