Limiting total number of records in a table with a nightly job
Thinking outside the box a little bit, but instead of a nightly job, what about a Table Trigger to handle it sooner so there's a much smaller batch to delete?
Basically you can have an after insert Trigger that checks the new size of the table, and deletes the amount of rows &gt; 3 million. I'd imagine this would always be 1 row since the Trigger would fire on every INSERT. Deleting 1 row should be very quick, but depending on the existing busyness of the table, I'm not sure if the additional contention for deleting will help or hurt more than a larger batch job at night. You'd have to test both ways and compare.

Another trick you could use is create an Indexed View on top of the table that only brings back the latest 3 million records, and do your querying off the View instead of the Table. Then the Table you can prune and archive less frequently, in a routine maintenance window perhaps.
As far as determining the latest 3 million rows, you can store the max value of your identity column of your Table in another Table that only has 1 row to keep track of this. Then in your View you'd INNER JOIN to that Table ON AuditTable.IdentityColumn &gt;= MaxAuditIdentityValueTable.Value - 3000000.
You can accomplish storing that max identity value a number of ways, one being an after insert Table Trigger as mentioned above. In this case, it should be an even more efficient Trigger because you're not locking your audit table when it fires (since you're not deleting from it), rather you're locking the MaxAuditIdentityValueTable instead, and since there's only 1 record to UPDATE in that table, it should be extremely fast. (By the way, please pick a better name than my example of MaxAuditIdentityValueTable, I suck at naming things. :)