Database – How to Delete All Tables with the Same Prefix

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).

The way I know is to use the following command either one by one:

RENAME TABLE tb1 TO my_prefix_tb1;

or

SELECT Concat('ALTER TABLE ', TABLE_NAME, ' RENAME TO my_prefix_', TABLE_NAME, ';') FROM information_schema.tables WHERE table_schema = 'my_database'

as described here

and then edit the app/etc/local.xml and find the tag with name <table_prefix> and update it accordingly <table_prefix><![CDATA[my_prefix_]]></table_prefix>, and save it.

You have to run these queries directly in the database so please please take a backup first or try on staging.