For a custom category filter like that you need to rewrite the class
Mage_Catalog_Model_Layer_Filter_Category, specifically the method
_getItemsData() that determines which values should be shown in the filter.
The relevant lines there are:
$categories = $categoty->getChildrenCategories();
You see that only children of the current category are taken into account, then it will be checked how many products of the current product collection are in each of these.
You need to replace
$categories = $categoty->getChildrenCategories(); but be careful, the whole collection gets loaded, so it's a bad idea to use all categories:
$categories = Mage::getResourceModel('catalog/category_collection');
(except if you only have a hand full of categories, then you can stop here)
So let's prepare this collection to only load the categories we need:
$resource = $categories->getResource();
$adapter = $resource->getReadConnection();
$productCategoryTable = $resource->getTable('catalog/category_product');
$select = $adapter->select()
->join(array('category' => $categoryTable), 'product_id=
->where('product_id IN (?)', $productCollection->getAllIds());
$allCategoryIds = $adapter->fetchCol($select);
There is still optimization potential, using joins in a single query instead of loading the product ids first, then the category ids, then adding the filter but this is not possible anymore with the Magento ORM alone, you'll need to manipulate the underlying Zend_Db_Select directly which will get a lot more complex. I'd try if this solution is sufficient and optimize when needed.