How to filter products NOT IN categories?

You need to join the table that holds the category/product relations.

A variation of the collection I use to find all products IN a list of categories should do the trick for you:

(untested, but should get you in the right track)

$productCollection = Mage::getResourceModel('catalog/product_collection')
    ->setStoreId(0)
    ->joinField('category_id', 'catalog/category_product', 'category_id', 'product_id=entity_id', null, 'left')
    ->addAttributeToFilter('category_id', array('nin' => $catIds))
    ->addAttributeToSelect('*');

$productCollection->getSelect()->group('product_id')->distinct(true);
$productCollection->load();

ref: http://www.proxiblue.com.au/blog/Collection_of_products_in_all_child_categories/

Following code will work for you:

$catIds = array(7,8,9);
$_productCollection = Mage::getModel('catalog/product')
                ->getCollection()
                ->joinField('category_id', 'catalog/category_product', 'category_id', 'product_id = entity_id', null, 'left')
                ->addAttributeToFilter('category_id', array('nin' => array('finset' => $catIds)))
                ->addAttributeToSelect('*');