This situation happens if you are removing products from magento non-magento way, so lucene index is not aware of that and is still trying to serve products which don't exists anymore.
Switch off module in administration (Lucene enabled on frontend to NO)
Remove var/indexer (in your magento root) folder completely
Reindex again (from SSH or using web browser)
Enable module again (Lucene enabled on frontend to YES)