You get a high-end Unix box and write the script, then do LOADS of recursive lookups on the non-referred whois (rs.internic.net) for domain status. Then you database the results twice a day, then repeat the cycle, then look for a registrar to partner with coz you ain't got a hope in hell of catching the drops on time. But this method WILL give you a list of domains pretty much as they are deleted. Catching them is another story...
Good luck!