1) What version of Exchange are you running?
2) Unified Messaging or voice mail only configuration?
3) Did you simply delete the Subscriber account from the Web SA? This only deletes the SQL data for the user. It doesn't delete the AD user or Exchange mailbox.
4) You can use the Data Link Explorer (CUDLE) tool on Unity Tools Depot to browse and run a query on the Subscriber table to see if the Subscriber is still referenced there.
Hailey