Magento EAV – Restore Deleted Attribute

The attribute is created by Mage_Catalog_Model_Resource_Setup, therefore you should be able to recreate it:

$installer->addAttribute(Mage_Catalog_Model_Product::ENTITY, 'manufacturer', array(
                    'type'                       => 'int',
                    'label'                      => 'Manufacturer',
                    'input'                      => 'select',
                    'required'                   => false,
                    'user_defined'               => true,
                    'searchable'                 => true,
                    'filterable'                 => true,
                    'comparable'                 => true,
                    'visible_in_advanced_search' => true,
                    'apply_to'                   => Mage_Catalog_Model_Product_Type::TYPE_SIMPLE,
                )
);

Throw this code snippet into one of your install scripts and this should do the job

Code is copied from here app/code/core/Mage/Catalog/Model/Resource/Setup.php:491

If you got orphan attribute values it means that there is something wrong with your database.
For example the table catalog_category_int has a constraint on the attribute_id column.

CONSTRAINT `FK_CAT_CTGR_ENTT_INT_ATTR_ID_EAV_ATTR_ATTR_ID` FOREIGN KEY (`attribute_id`) REFERENCES `eav_attribute` (`attribute_id`) ON DELETE CASCADE ON UPDATE CASCADE,

This means that if the attribute is deleted, all the values for the attribute from the table catalog_category_int will be deleted.
It's the same for the rest of the tables (catalog_category_*).

From experience I saw that usually constraints are lost during a migration process. You export the database but without the constraints. If this is the case then remember in the future to use System->Tools->Backupto create database dumps for migration.

[EDIT]
Here is the code I've used. I've created a simple extension that adds an attribute to the category entity, I edited a category and filled in a value for that attribute, then deleted the attribute through an upgrade script.
Here are the extension files:

app/etc/module/Easylife_Attr.xml - declaration file

<?xml version="1.0"?>
<config>
    <modules>
        <Easylife_Attr>
            <codePool>local</codePool>
            <active>true</active>
            <depends>
                <Mage_Catalog />
            </depends>
        </Easylife_Attr>
    </modules>
</config>

app/code/local/Easylife/Attr/etc/config.xml - the configuration file

<?xml version="1.0"?>
<config>
    <modules>
        <Easylife_Attr>
            <version>0.0.1</version>
        </Easylife_Attr>
    </modules>
    <global>
        <resources>
            <easylife_attr_setup>
                <setup>
                    <module>Easylife_Attr</module>
                    <class>Mage_Catalog_Model_Resource_Setup</class>
                </setup>
            </easylife_attr_setup>
        </resources>
    </global>
</config>

app/code/local/Easylife/Attr/sql/easylife_attr_setup/install-0.0.1.php - the install script

<?php

$this->addAttribute('catalog_category', 'dummy', array(
    'group'         => 'General',
    'input'         => 'textarea',
    'type'          => 'text', //can be any type
    'label'         => 'Custom attribute',
    'backend'       => '',
    'visible'       => true,
    'required'      => false,
    'visible_on_front' => true,
    'global'        => Mage_Catalog_Model_Resource_Eav_Attribute::SCOPE_GLOBAL
));

Now add a value for this dummy attribute for a category.
You should see it in the table catalog_category_entity_text.

After that create an upgrade script to remove the attribute. app/code/local/Easylife/Attr/sql/easylife_attr_setup/upgrade-0.0.1-0.0.2.php

<?php
$this->removeAttribute('catalog_category', 'dummy');

and change in config.xml the version from 0.0.1 to 0.0.2.

Refresh any page and look in the same table catalog_category_entity_text. The value that was added for the dummy attribute is gone. (at least for me).