Why is MySQL choosing that index? I have a large indexed table with over 35 million rows. Here are the indexes, with a naming convention that shows their sequential column order:

IDX_E93438363DAE128B,
IDX_LIST_ID_EMAIL_ADDRESS_DELETED,
IDX_LIST_ID_SUBSCRIBED_DELETED_EMAIL_ADDRESS,
IDX_LIST_ID_SUBSCRIBED_DELETED_FIRST_NAME,
IDX_LIST_ID_SUBSCRIBED_DELETED_LAST_UPDATED_AT


My query of this table on my medium Amazon RDS instance is taking upwards of 15 minutes:

SELECT * FROM contact
WHERE list_id = '014c7cbe-c124-11e5-b4ea-0a4287b2e8c5'
AND subscribed = 1
AND deleted = 0


Using an EXPLAIN of the query I can see that MySQL is choosing to use the IDX_LIST_ID_EMAIL_ADDRESS_DELETED key, when I'd expect most of the other keys (IDX_LIST_ID_SUBSCRIBED_DELETED_...) to be more optimal.

Should I just trust the engine? Is 17 or so minutes a realistic time to wait for a query on a table this large?
17 minutes is not a reasonable time to wait. Try to provide an index hint:

SELECT *
FROM contact USE INDEX (IDX_LIST_ID_SUBSCRIBED_DELETED_EMAIL_ADDRESS)
WHERE list_id = '014c7cba-c124-11e5-b4ea-0a4287b2e8c5'
AND subscribed = 1
AND deleted = 0