Another approach to looking up the categories a product has is to store the url of the category a customer has last viewed into the session. This follows the assumption that most users would go to a category page > product page > cart.
An example of how to store and retrieve the url would be to add this to your catalog/category/view.phtml
template
$currentUrl = $this->helper('core/url')->getCurrentUrl();
$session = Mage::getSingleton("core/session", array("name"=>"frontend"));
$session->setData("last_category", $currentUrl);
Then on the cart page template (checkout/cart.phtml
) you can retrieve the url like so:
$session = Mage::getSingleton("core/session", array("name"=>"frontend"));
$lastUrl = $session->getData("last_category");
You may also want to take into account if they never visited a category page & provide fallbacks such as you stated in the question of using one of the categories of a last added product, or simply sending them back to the home page or a featured category page.
Update:
To get the a category URL of the last added product from the same store you can compare the path to the root category ID of the store:
$lastProductAddedToCartId = Mage::getSingleton('checkout/session')->getLastAddedProductId();
$continueShoppingCategoryUrl = Mage::getBaseUrl();
if($lastProductAddedToCartId) {
$productCategorys = Mage::getModel('catalog/product')->load($lastProductAddedToCartId)->getCategoryCollection();
$rootCatId = Mage::app()->getStore()->getRootCategoryId();
foreach ($productCategorys as $category) {
$regex = "/^[0-9]+\/". $rootCatId . "\/[0-9]+/";
if(preg_match($regex, $category->getPath())){
$continueShoppingCategoryUrl = $category->getUrl();
break;
}
}
}