Oh- thanks; I don't know why I didn't think of that! Yes, of course, that seems obvious now. Our server doesn't have much memory, so naturally we woud run out of room by choosing APC as the message index cache.
I've now changed the first setting to 'db' (database) for the cache. That'll allow plenty of room for unlimited caching, and I'll take a look in a few days to see if that fixed it.
Many thanks for the suggestion!