Zend certified PHP/Magento developer

Magento 1.9 add to cart slow when cached

We have been experiencing an odd issue on some of our sites since moving from Magento 1.7 to 1.9. When a sites cache hasn’t been cleared for a while add to cart is extremely slow. This also affect the checkout. As soon as we clear the cache it speeds up again.

I can not really make sense of why this happens. I have tried profiling to see what it is that takes a long time and it seems that the culprit is the cleanModelCache function that cleans the following cachetags

[0] => quote
[1] => quote_1002 (quote_ID)

This function is run twice during the add to cart and it takes about 5 seconds each time.
If I clear the cache this is instant.

I am not super knowledgeable exactly how the magento caching is built up but it feels odd that it would take this long to clear a cache tag irregardless of how big the cachefolder is.