Not sure whats going on but when it comes down to deleteing contacts, dont bother I have 525 contacts and my ICQ works fine.
But you should be able to use trillian, and just dont unistall your old ICQ will save the historys and you can dig them up as you need them and Trillian saves history also.
