Seth,
You could certainly write a program using the Platform SDK to poll a folder of documents, though the documents would need to have an index file with them (e.g. a "dwcontrol" file). The program could access the database and verify non-duplication, then upload the document.
If your client is OK with modifying the underlying database, what would happen if you declared the combination of the fields in question as a unique index at the SQL Server system level? I am not sure what would happen if SQL Server simply refused to allow the insert because of such a constraint, but it might perform fewer locks than a trigger (I am not a SQL Server expert).
If the client does not like the overnight check idea, could you run the check hourly? Even half-hourly? A read-only query of 500,000 records should run really quickly, and so could detect duplication issues often and efficiently (I assume the index fields you check for supes on are indexed).
EDIT: Here is a link to creating a unique, multi-column constraint, which is maybe what you are already doing:
https://stackoverflow.com/questions/1670708/how-to-create-composite-unique-constraint-in-sql-server-2005
Thanks,
Joe Kaufman