How to handle deprecated "Mysql4" classes when rewriting resource models

deprecatedNode is used by Magento to try and load mysql4* resource model if resource* wasn't found. Reference the comments from Mage_Core_Model_Config::getGroupedClassName and Mage_Core_Model_Resource::getEntity:

/**
 * Backwards compatibility for pre-MMDB extensions.
 * In MMDB release resource nodes <..._mysql4> were renamed to <..._resource>. So <deprecatedNode> is left
 * to keep name of previously used nodes, that still may be used by non-updated extensions.
 */

If there is resource* model you should rewrite it, otherwise rewrite mysql4* one. Example of rewriting mysql4* resource model:

<config>
    <global>
        <models>
            <review_mysql4>
                <rewrite>
                    <review_collection>AW_AdvancedReviews_Model_Mysql4_Review_Collection</review_collection>
                    <review>AW_AdvancedReviews_Model_Mysql4_Review</review>
                </rewrite>
            </review_mysql4>
        </models>
    </global>
</config>

The mysql4* classes are only there for backwards compatibility for existing implementations which already extended them. I.e. shell classes to avoid forcing existing code to update the extends on everything to continue working.

If you develop an extension for personal use that is supposed to work only for you project build on Magento 1.6+ then there are no worries. You should only override Mage_Catalog_Model_Resource_Category_Flat by adding this in the config.xml file of your extension:

<models>
    <catalog_resource>
        <rewrite>
            <category_flat>Namespace_Module_Model_Resource_Category_Flat</category_flat>
        </rewrite>
    </catalog_resource>
</models>

If you are building an extension and you want it to work on version before 1.6 you need to override the Mage_Catalog_Model_Resource_Eav_Mysql4_Category_Flat class also. In this case your config.xml section should look like this:

<models>
    <catalog_resource><!--used for 1.6+ -->
        <rewrite>
            <category_flat>Namespace_Module_Model_Resource_Category_Flat</category_flat>
        </rewrite>
    </catalog_resource>
    <catalog_resource_eav_mysql4><!-- used for versions before 1.6 -->
        <rewrite>
            <category_flat>Namespace_Module_Model_Resource_Eav_Mysql4_Category_Flat</category_flat>
        </rewrite>
    </catalog_resource_eav_mysql4>
</models>

You should put all your logic in Namespace_Module_Model_Resource_Category_Flat and the class for versions before 1.6 should look like this:

class Namespace_Module_Model_Resource_Eav_Mysql4_Category_Flat extends Namespace_Module_Model_Resource_Category_Flat
{
}

This way both versions use the same code.