As a bit of a side interest on this problem, does this table suffer from any INSERTs from a GUI?

If so, are the INSERTs done in order by [SubscriberID],[UserID],[DeviceID] ?

I...

Using a temp table, indexing the temp tables using a covered index and selecting from the temp table worked extremely well. The merge is down to 20 minutes. ...

Thanks for the help. I will try the temp tables, indexing the temp tables and using the covered index.

The table scan actually doesn't take that long. I ran the "select" part of the merge statement and that part returned 10M rows into a temp table is 4...

Thanks for the reply. I attached the explain plan for your review. The three varchars are a necessary join. I'll look into the links you provided.