In general, lookups are performance killers in DTS packages.

If I were using DTS against millions of records, I'd not use a lookup.  Could you add the foundkey in your source SQL?