I have updated the statistics, but I don't know if I did FULL SCAN or not. Most likely I have not.
SELECT DISTINCT TOP 10
FROM sales s
INNER JOIN locations l ON l.location_key = s.delivery_location_key
INNER JOIN builds b ON b.transaction_key = s.sale_key AND b.transaction_type = 'SAL'
INNER JOIN build_details bd ON bd.build_key = b.build_key
INNER JOIN outbound_shipments os ON os.outbound_shipment_key = bd.outbound_shipment_key
INNER JOIN freight_carriers fc ON fc.freight_carrier_key = os.carrier
l.country_code = 'US'
AND l.state = 'NY'
AND s.status != 'CAN'
AND b.status != 'CAN'
AND os.status != 'CAN'
ORDER BY s.sale_key DESC
Wasn't sure how to post that, so here is a link to a screengrab: http://dl.dropbox.com/u/143275/distinct-top-5-execution-plan.png
On builds: nonclustered on transaction_key and transaction_type
On build_details: nonclustered on outbound_shipment_key
The largest table is build_details with 311k records. All the others are under 20k.