New content type not listed in content types
The problem you're facing is producing symptoms very similar to the ones in this bug. Especially because one of the symptoms you mentioned is that after you create any new content type with the same machine name that had a problem ('address' in your case) you get the message: 


  The content type XXX has been updated


This issue is because one of the content types that you previously created originally had a machine name of 'address' but was renamed to something else. This is because Drupal actually preserves the original machine name of any content type in the DB Table named "Node_Type" in the column "Orig_Type". 

Firstly, I suggest that you open the "Node_Type" table and try to investigate. You will most likely find that one of the listed Content Types has 'address' in its "Orig_Type" column.

The bug I've linked above contains patches in order to prevent this kind of issue from happening in the future. Unfortunately, in your case, the issue had already happened and you must now clean-up.

I'm not an expert in this field as I've only been involved with drupal for 6 months. However, I'll try my best to list the steps you need to do to remedy the issue. Note that there may be better/cleaner methods than the ones I've listed below so please be cautious:

Step 1 - Please carefully investigate the "Node_Type" table in your Database as I've mentioned above before proceeding. You may be facing a different issue and this solution may or may not work in that case.

Step 2 - Backup your Database before proceeding

Step 3 - Please try to perform one of the following procedures, preferably in order until one of them works for you:

A. Try the Deletion URL


Try to go to the URL YOUR_SITE/admin/structure/types/manage/MACHINE_NAME/delete and delete the content type
Check the "Node_Type" table to see if the problematic content type was deleted.


B. Programatic Deletion


Try to programatically delete the unwanted content type by running node_type_delete($type) and then optionally node_types_rebuild(). In order to use these 2 functions in a module you must use the hook_node_info(). Something similar to this code may work in your module's ".module" file:



&lt;?php    
function MYMODULENAME_node_info()
{
  node_type_delete("address");
}




Check the "Node_Type" table to see if the problematic content type was deleted.


C. Manually Replicate node_type_delete($type)


Visit the node_type_delete($type) hyperlink, and carefully read all the functions that it invokes. They are all clickable hyperlinks too.
Either write code to use each of its functions individually.
Or, replicate the actions that all the functions perform exactly and manually in your Database.


@Mods. The site restricts me from posting more than 2 hyperlinks because of my reputation, so apologies for lack of links.