Back on the subject - found (I guess) the solution
Issue is related to Lock Striping (cfr. http://community.jboss.org/wiki/LockingandConcurrency#Lock_striping)
According to the documentation, lock striping is enabled by default.
Lock striping entails the use of a fixed-size, shared collection of locks for the entire cache, with locks being allocated to entries based on the entry's key's hash code. This means two different keys may share the same lock - which is the case in my example.
I disabled lock striping and my test now runs fine (or at least as expected).
Conclusion: in you fine fine-graine lock, then either disable lock striping or carefully choose your hashcode generation for the keys...