You should also be doing EXPLAIN for each of your queries, to verify that the indexes are being used in the expected manner.