KCFinder sometimes won't upload images
Sounds like a combination of a slow-ish server/network, too many images and possibly some configuration bits.

The KCfinder runs in a little popup window that makes it extra difficult to diagnose, and tries to load thumbnails of all your existing images so you can select one. All that work is overloading both your network and your server (and maybe even your browser, though unlikely).

You may be able to customize kcfinder so that it's not generating quite so many thumbnails, and/or fix your server so that it doesn't have to do it each time (i.e. with some caching, though that's a bit tricky, e.g. ensure you have mod_expires enabled with apache).

You're right that you're somewhat painted into a corner, and a more powerful server might be the easiest solution.

Alternatively, you could set up a separate directory for old images and move over ones that are more than a month old.

Going forward, you may also want to make sure you're not uploading really large images, i.e. scale them on your own machine before uploading them.