Here's a working single query solution:

$categoryId = 46;

/**
 * Create select that returns only product ids that are either
 * in the specified category or any of it's subcategories
 **/
/* @var Mage_Catalog_Model_Resource_Category_Collection $productCollection */
$categoryCollection = Mage::getResourceModel('catalog/category_collection');
$excludeProductIdsSelect = $categoryCollection
    ->getSelect()
    ->reset(Zend_Db_Select::COLUMNS)
    ->join(
        array('ccp' => $categoryCollection->getTable('catalog/category_product')),
        'e.entity_id = ccp.category_id',
        array()
    )
    ->where('path LIKE CONCAT(\'%/\', ?, \'/%\')', $categoryId)
    ->orWhere('path LIKE CONCAT(\'%/\', ?)', $categoryId)
    ->columns(array('ccp.product_id'));

/* @var Mage_Catalog_Model_Resource_Product_Collection $productCollection */
$productCollection = Mage::getResourceModel('catalog/product_collection');

/**
 * Join excluded ids and select only products for which ids where not found
 */
$productCollection
    ->getSelect()
    ->joinLeft(
        array('epi' => $excludeProductIdsSelect),
        'e.entity_id = epi.product_id',
        array()
    )
    ->where('epi.product_id IS NULL');

/* Get the result */
var_dump($productCollection->getData());