SQL Server: query performance (search 2 million rows)
Without indexes, any time  the search query is run, all 2 million records have to be searched to find the 650K 'FR' instances.  With indexes, the database can essentially go straight to them.  Even if you left the search query as-is, I think proper indexes would give you speed improvements.

As far as the temp table, I really don't see why that couldn't be done as a sub in the final results query.  Aside from that, I think temp tables would be more useful for persistent connections to the DB, or pools of users.  If you're just creating the temp table and immediately destroying it... then it's basically just being used as a subquery.

Update: M_M makes a good point in his comment on this answer.  However, I still feel an index would be better if the majority of activity is not just on sets where country is the only criteria.  For me (just my opinion) it would come down to how often the 'FR' subset would be needed by itself with no other criteria.  Otherwise, indexes could be used in the marjority of the searches.