Deleting contacts from your ICQ contact list is problematic in itself.
When I delete one, I delete the history also, and this process tends to use up the majority of my computer resources. I have no idea why it needs so much. It would take a couple hours for me to individually remove users from my list.
The other problem is that they sometimes magically re-appear the next time you start your ICQ. Maybe the best solution is to get a new account altogether.
Threaded Mode