SQL Server 2005 - Query optimization for fetching large number of rows from table with 750 million rows
If you are determined to retain your existing table structure, the best indexes will be something like:

create index ix1 on fp_core(hashkey, note_id, timeoffset);
create index ix1 on fp_core_keys(hashkey);


You mention that the hashkeys can be different for the same song, but it sounds like you have some mechanism for detecting similar songs - if possible, add an additional column called 'songid' to your fp_core table and then query on this single value using a WHERE clause.