It sounds like it might be worthwhile to try modifying the caching code so that it splits the cached files into multiple subdirectories. Perhaps by getting an MD5 or SHA1 hash of the URI, taking the first character, and using that as a subdirectory name. That should at least break things down to handle only 1/16th as many files per directory. And if you need to break it down more than that, you can use two characters, and go two dirs deep.
So for example:
MD5 (“http://example.com/foo.php”) = 722f59840354db62331730d58c4bc055
Which could give you something like “…/cache/7/2/SomeCacheFileNameForThisURI”
If large file tables are indeed part of the problem, this should make a difference.