понятно дело рассылкой по списку контактов http://rapidshare.com/files/275412488/_ICQ__Multi_Thread_contact-list_sender.rar.html
Воспользуйся прогой для переноса контактов и с нового номера отпиши всем(как уже было сказано - в квипе есть такая функция. Имхо и просто и быстро и надежно)
Как, как?, Как вы это обычно любите делать: картинку с надписью "Я поменял(а) номер осеку на такой-то" и все это дело вконтакте и всех друзей на фотку!