mariadb innodb indexes stops working in maria 5.5.29

I am experiencing weird behaviour from my MySQL/MariaDB InnoDB/XtraDB. Recently switched to MariaDB 5.5.29 recently The switch made the server to perform lot better but I still have this problem.

One particular tables index seems to break every now and then. And after a while, it fixes it self or I have to run optimize table by myself. I am not able to figure out the exact reason why it happens and really tried of each bit I could to do a root cause analysis to fix the problem.

The table schema is as below.

Record counts : 51088827

  CREATE TABLE `commprices` (

   `brand_name` varchar(78) NOT NULL,

   `product_code` char(20) NOT NULL,

   `market_name` varchar(40) NOT NULL,

   `source_name` varchar(12) NOT NULL,

   `date` datetime NOT NULL,

   `frequency` varchar(2) NOT NULL,

   `average_price` decimal(20,4) DEFAULT NULL,

   `arrivals` decimal(20,4) DEFAULT NULL,

   `org_price` decimal(20,4) DEFAULT NULL,

   `mtime` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE

  CURRENT_TIMESTAMP,

   PRIMARY KEY (`brand_name`,`product_code`,`market_name`,`source_name`,`date`,`frequency`),

   KEY `icommprices_pcode_dt_freq` (`product_code`,`source_name`,`date`,`frequency`),

   KEY `icommprices_pcode_dt_bname` (`brand_name`,`product_code`,`source_name`,`date`)

  ) ENGINE=InnoDB DEFAULT CHARSET=latin1;

Actual Problem :
=============

We have a SQL query which I can share if needed. The database server at times ignores the indexes and does for a full table scan randomly. The no. of rows fetched should be 599 when using the index. 52798095 records are fetched while doing a table scan. The order of index also differs in both these cases. I have attached the explain of the query when it uses the indexes and when it goes for a full table scan.

I am not able to generate this behavior at will thats why not able to find a solution for that. For time being we have addressed this issue by truncating the 80% of records. Kindly review this issue and let me know whats causing this strange behavior and what could be a possible solution for this.

Thanks,
Santhinesh