Tonizz:
If you delete a rendition, the source XML will also be deleted as well.
If you do not submit the deletion, however, and commit to Staging, our Lucene index is *not* updated. That index is used to determine what to regenerated. So, if you delete something and do not submit, the search will return your deleted item as something to regenerate, but when it tries to will find that you've a modified, deleted version in your sandbox. I think that that is the result of your error.
How to resolve? When you delete something, submit it. Then, regenerate should work A-OK.
Kevin