KMix becomes gradually slower if you leave it running for a while... it's been that way on Kubuntu since 4.3 at least. Using pulseaudio here.
By slower I mean that changing the volume is laggy, unresponsive.

I even have a script that kills kmix and runs kmix --keepvisibility every two hours. Is anyone else experiencing that?

I experience an increase in KMix memory usage over time, but certainly not increasing slowness. Are you able to reproduce under a new user? If you cannot, your KMix configuration may be damaged and thus causing this.

It does increase in memory usage as well. I don't know about a new user, but since this started happening, I've deleted my ~/.kde a couple of times to no end.

I also am using USB headphones which may be related.

The usage of extra audio devices such as headsets, microphones, etc shouldn't have any effect. Trying under a new user would be best at this stage, to determine if any element of your user profile could be causing this.