My suggestion would be not to start changes indexes yet. If the query was working at one time and has stopped that smells like indexes and\or statistics are in tough shape. Additionally, estimated execution plans can be unreliable. Try to get the actual plan, adding a top 1 to the select should do that for you.

Run this command this two commands during low server load and post the results

dbcc showcontig('table_name_here') with all_indexes

dbcc show_statistics('table_name_here', 'index_name_here')

Run the second command for each table and every index. Run the first command for both tables.

Once you post the results I jump on and look at them for you.

David