With 1,000,000 advertisers and $500K per month...hire someone to write a script for you!!!
I wrote a script that automatically deleted ads when they expired and also emailed the customer to let them know it expired (which more often than not resulted in a repeat sale). This is hugely trivial. The ad details, including the expiry date and the customer's email address are in the database. A script running daily by cron picks out the ads that have expired, then deletes them (or marks them inactive...depends how you're doing it) then emails the customer.
I also had a service that was paid by PayPal subscription. If a payment isn't made or a subscription is canceled, you get a notification from the PayPal IPN (Instant Payment Notification). Again, hugely trivial to delete a record or mark as inactive.
Seriously, there is nothing to this, and with your numbers, a "no brainer".