How to Allow Multiple Billing Countries but Restrict Shipping in Magento

You can do the same without a rewrite using an observer:

<sales_quote_collect_totals_before>
    <observers>
        <your_module>
            <type>singleton</type>
            <class>your_module/observer</class>
            <method>salesQuoteCollectTotalsBefore</method>
        </your_module>
    </observers>
</sales_quote_collect_totals_before>

Then, in the observer:

public function salesQuoteCollectTotalsBefore(Varien_Event_Observer $observer)
{
    /** @var Mage_Sales_Model_Quote $quote */
    $quote = $observer->getQuote();

    $store = Mage::app()->getStore($quote->getStoreId());
    $store->setConfig('carriers/tablerate/name', 'Name By Country');
    $store->setConfig('carriers/tablerate/title', 'Method Title By Country');
}

Setting the config values dynamically without saving them is a cheap trick but it works pretty well.
The benefit of using an observer over a class rewrite is that it's less conflict prone.

I believe Magento has already solved this by limiting shipping methods by destination country:

System > Config > Shipping Methods > [Method]

All that would be needed is some messaging on checkout in the shipping destination entry and shipping method selection areas which would notify which countries you ship to.