Actually it happened again, this time with Psi and nothing in the logs so far. It’s a bit scary, since there is no sign that contacts get lost (i.e. some error) and just lead to the belief that some users aren’t online for days.
Anyway, randomly deleted contacts are a serious showstopper, especially with these UINs ICQ uses.