what is the error message?
you cannot simply remove a voice mail subscriber and add them back with the same alias.
when you only delete the subscriber from unity, the alias still exists in AD and either must be removed before recreating the new subscriber or a new alias must be used.
a good way to remove all pieces of a unity subscriber, including the AD alias, is to use the AD exchange tasks or manually delete the AD alias, unity subscriber and exchange mailbox.
please see the following link for more info deleting subscriber accounts and the impact on exchange 5.5 vs exch 2000/AD:
http://cisco.com/en/US/products/sw/voicesw/ps2237/products_administration_guide_chapter09186a008022c917.html