The cause of the problem was that we started using View#setTag(int,Objec) and it wasn't very obvious why this problem happend.
After looking at the source code of View it turned out that the indexed tags are stored in
private static WeakHashMap
Where the key is the view itself and the value are the indexed values. While I have no idea what has caused this design choice it doesn't seem to be a big problem. BUT we stored ViewHolder like structures in it which indirectly referenced the view itself!
Because of this the key was never removed by the GC because it was still referenced by the value. To understand the issue you have to know the implementation details of View - otherwise you are absolutely lost and there is no hint found in the docs.
I hope I will always remember that using View#setTag(int,Object) is a tricky thing and I hope I will never ever store a reference to the view itself as a value.