The optimization process and recommendations:

1. Create Optimal Indexes (modified query below): The recommended indexes are an integral part of this optimization effort and should be created before testing the execution duration of the optimized query.

Optimal indexes for this query:

ALTER TABLE `item_properties` ADD INDEX `item_properties_idx_prop_id_item_id` (`prop_id`,`item_id`);

The optimized query:

SELECT
        items.stuff 
    FROM
        items 
    WHERE
        EXISTS (
            SELECT
                * 
            FROM
                item_properties 
            WHERE
                item_properties.prop_id = 123 
                AND item_properties.item_id = items.id
        ) 
        AND EXISTS (
            SELECT
                * 
            FROM
                item_properties 
            WHERE
                item_properties.prop_id = 456 
                AND item_properties.item_id = items.id
        ) 
        AND NOT EXISTS (
            SELECT
                * 
            FROM
                item_properties 
            WHERE
                item_properties.prop_id = 789 
                AND item_properties.item_id = items.id
        ) 
        AND NOT EXISTS (
            SELECT
                * 
            FROM
                item_properties 
            WHERE
                item_properties.prop_id = 101 
                AND item_properties.item_id = items.id
        )