Actually, there is a feature "Delete all contacts" that deletes them and does not touch IM lists. It's just a bit hidden under the "Contacts"-->"Settings" and I did not notice it at first. My problem occurred when I manually deleted the contacts, by selecting them 10-30 at a time and using general contact deletion button.