How Do I delete lingering user objects in Active Directory

We recently deleted a user account who had an email attribute. We later recreated that user back again. But what we found was that, emails sent to that particular address were bouncing back (undelivery), thus the recipients address was not found in the mail system.
How can this error be corrected?.. Thanks.