Max allowed packet size could be one reason this is happening, but I can see multiple reason why it is probably something else in this case.
- You don't just have cache writes, you also have explicit cache deletions. A failed cache write would just result in repeating cache writes and then cache misses, but not deletions.
- This is the cache_bootstrap table. There are some caches that can get big but they're usually not from that bin.
The most common reason for this pattern are variable_set() calls that happen on every page. Have a look at the where those cache deletions are coming from, either with xhprof, with xdebug and setting a breakpoint or by adding a debug_print_backtrace(DEBUG_BACKTRACE_NO_ARGS). I'm pretty sure that you will see a variable_set() call there.
The problem is that there is a single global cache for variables. Every cache write results in a cache delete and the next request will read out the whole {variables} table and write it back into the cache.
Many developers aren't aware of that and are doing things like "ensuring values" by calling variable_set() directly in a .module file or another place that is executed on every request.
