Try Noroom's Listmanager, with that you can clean up your contactlist (like delete ppl from the allowlist wich you don't have on your contactlist anymore and deleted you too...clean up the blocklist, you might have ppl onthere that don't have you on their list anymore).
Do you have hotmail MSN ID ? Then you have to delete contacts, you deleted from MSN, also from hotmail address-book. You should be able to add new contacts after doing this.