Hi Megame!

Try also to check with your webhosting company what kind of error message is delivered to the googlebot when it tries to re-index deleted pages. Preferably you should go for a 301 (permanently moved) error message guiding the googlebot and other visitors to an error-page you make for this situation and other types of missing pages on your site.

Installing Google Sitemap also helps with faster re-indexing.

Good luck

Iggyjac