WHERE NOT IN SQL Performance

SELECT TOP 1 l.ID 
FROM Leads l
WHERE 
     l.ID NOT IN (SELECT LeadID FROM LeadFollowups) 
     AND l.ID NOT IN (SELECT LeadID FROM LeadsWorking)
     AND l.ID NOT IN (SELECT LeadID FROM LeadsDead)
     AND l.ID NOT IN (SELECT LeadID FROM LeadHolds)
     AND l.ID >= (RAND() * (SELECT MAX(ID) FROM Leads))
ORDER BY l.QualityScore DESC

I have a table growing by a 10 to 100 thousand rows a day. I have several tables to track actions of the current leads that shouldn't be included when grabbing the new lead. My query is pretty quick now, but as this grows is NOT IN the most efficient solution for this? Especially if I get in to the range of ~10 million rows in the Leads table?

My query is pretty quick now, but as this grows is NOT IN the most efficient solution for this?

I expect it would be quicker if you had an indexed Status field in the Leads table (so that records in the LeadsDead table had a corresponding Status=Dead in the Leads table); and quicker still if Status were a clustered index, so that all the leads with a given Status were contiguous in the Leads table.

StackExchange Code Review Q#42781, answer score: 6