Just an update on this :
We have used profilers and every trick under the sun to determine what is happening. We have found that we may not actually have a deadlock at all, but the jvm slows down acutely and causes backlogs in our cache queues. (memory and all other external indicators look ok).
We have downgraded to java 6 update 14 (we were using the latest update 20) and it seems to be fine now. I will continue monitoring the situation, and when I am convinced that it is the latest update that caused the issue, I will take it up with Oracle. As I must stress now, this is only speculation.