Kim, The first thing I'd do is run a MyISAMChk on the table to see if the index is damaged. The second thing I'd do is run Optimize on the tables regularly because after a lot of rows have been deleted it leaves holes in the table which slows down table performance.

Of course you can do an Explain on:

select * from products LEFT JOIN items ON products.product_id = items.product_id WHERE items.product_id IS NULL;

to see if it is using the index. And finally turning it into a Subselect might speed it up. (Yes, subselects can run faster than table joins in some cases)

Mike