SQL - improve NOT EXISTS query performance

Off the top of my head, you could try something like:

 TRUNCATE temptable
 INSERT INTO temptable ...
 INSERT INTO temptable ... 
 ...
 INSERT INTO realtable
 SELECT temptable.* FROM temptable
 LEFT JOIN realtable on realtable.key = temptable.key
 WHERE realtable.key is null

Make sure you are searching on indexed columns, with no manipulation of the data within those columns (like substring etc.)

Try to replace the NOT EXISTS with a left outer join, it sometimes performs better in large data sets.