It seems I did not test the new caching well enough, and there were several bugs involving updating. At first, updating did not work (or rather, the updated results did not show up as the cache was not dirtied). Then, just today, I found another bug, involving editing working, but the results showing up only in edit mode - which is of course not optimal.
I solved the problem, fortunately. I replaced the actual caching system with a new one which is a hybrid between active and lazy caching. Active caching is used in every store and delete action to invalidate other entries, and lazy caching is used with all gets to validate entries being requested.
And, this system seems to work much better. And, as a bonus, it is even faster than the previous one!