Deleted duplicate contact, when try to make login still says the email address is already registered ((Drupal 7.53, CiviCRM 4.6.24)
When you check availability, it's actually not looking at CiviCRM - it's looking in Drupal.  If you're a coder, you can read the code here.  Based on this, it seems like you need to delete the Drupal user, not the CiviCRM contact.

To fix:


Go to CiviCRM menu » Hide menu to view the Drupal menu (see screenshot).





Your Drupal menu may vary based on the installed extension, but you'll likely have a "People" menu:




From here, you can delete the Drupal user.  Instructions can be found here.

Note that if you create a new Drupal contact with the same email address as a CiviCRM contact's primary contact, the link between the two will be regenerated!  So you should never have to delete the CiviCRM contact in this instance.