Aaaaah, I thought your business methods are part of Data... You should have mentioned that from the start
This is what made me think that the code from the first post is inside your Data:
In my implementation all methods are marked synchronized, so when lock is called and record is valid a RNFE being thrown by read/update/unlock could never happen.
From here, I (mis)understood that the code you posted is also synchronized and inside Data.
Now, since your Data is also your lock manager, I understand that when the thread wakes up it will check again if the record is still valid, and won't lock unless it's valid (that's why you don't have to call unlock()).
I'd say IllegalStateException. I wouldn't create a new exception just for wrapping an exception that should never occur. As for assertion, it might also be appropriate, just that in these complex situations, involving threads, I wouldn't trust an assertion. And it's against the principle of "never swallow and exception".
Or... you could disable the re-check inside lock() and let update() check for itself, and you don't have to worry about this issue anymore
(Anyway, you'll have to wonder "why did SUN plant this Exception in my interface if it should never be thrown?")
And, again, sorry for the misunderstanding... It's just that I'm not used to giving answers without first seeing if the problem is real or not (or if there are no other problems instead), and only afterwards answering (if there's anything left to answer).