MySQL Join Problem - WHERE NOT IN

Using MySql 5.1.30.

I have an order_history table and a order_history_products table.  The products table has many rows for each order in the orders table.

I need to know what orders do not contain certain products, for example:

SELECT * FROM `order_history` WHERE order_id NOT IN (SELECT  order_history.order_id
      FROM order_history INNER JOIN order_history_products ON order_history.order_id = order_history_products.order_id
      WHERE order_history_products.product_name = 'Pencils'
      GROUP BY order_history.order_id)

In theory this query would work, but the query takes 10+ minutes to execute.

If I execute the query separately it takes only seconds to finish (the inner join).

Example of tables:

---order_history---
row 1
{
    order_id: 5000
    order_fullname: John Doe
}

---order_history_products---
row 1
{
    order_id:5000
    product_name: Pencils
}
row 2
{
    order_id:5000
    product_name: Paper
}
row 3
{
    order_id:5000
    product_name: Paperclips
}


-----------------------

Also, in the orders_history table, there are multiple rows for the same customer, so I'll be grouping the end result by order_fullname.  Just FYI.

I'm open to any suggestions, even reconstructing the structure if necessary.

Thank you.