Since you currently have listings in google, you could always follow the "KISS" principle.

Create your own site-map page (not for submitting to google), pull the results out from the database and list the items as direct links to the products.

Then as part of your navigation, even if its part of your footer navigation, put a link to your new site-map page. So once the search engines spider your site and see the new site-map link they will spider that page and access all of your products.

Instead of deleting product pages once they are sold, it would a better idea to simply disable the online selling process for that item (if its ecommerce) and put in red letters "SOLD". This way visitors can see that at one time you did sell the item they are looking for and it will prompt them to search your website for similar items.