mySQL efficiency with inner join queries
Based (only) on your query i think the better query could be :

 SELECT table_a.record_id from table_a
 INNER JOIN table_b ON (table_a.record_id = table_b.cat_id)
 WHERE table_a.customer_id = "654" and table_b.customer_id= "654"
 GROUP BY table_a.record_id
 HAVING COUNT(*) &gt; 1;


the correct index could be in   table a  only this: 

KEY cust_and_rec (customer_id, record_id)


in table b only 

KEY cust (custmer_id)


In the index you show in your question seem rc, test and test2 are the same and not  so selective like the inverse (customer_id is the most selective value in your query )

index rc on table b seem not useful for your purpose.