Thanks for the bug report. In layman's terms what seems to be the problem is that when you "delete" an item in assets it isn't actually deleted permanently, rather it is hidden from view. The intention is that at some point we would introduce a Trash Can for assets in the same way as we have for content.
So, currently these deleted items are living inside an "invisible" Trash Can.
However, although the items are not visible to the public, it seems the Whole Site search inside the Assets Library is returning them.
We will provide a fix for this soon.
Joe - Voice Admin