There were a few posts earlier about this but none seemed to end in a resolution. When a VM is destroyed the disks don't get deleted by oVirt and are left in an "illegal" state. Manual intervention is required to delete the image and remove it from the database.
This has only happened recently, but I'm not sure what broke it. I assume it's the engine which handles the deletion of the disks. Here's a snippet of the log, where 78605656-f77c-4b72-843b-1 is the image id
cat engine.log | grep '78605656-f77c-4b72-843b-1'
2013-10-24 21:12:33,141 ERROR [org.ovirt.engine.core.bll.RemoveAllVmImagesCommand] (pool-6-thread-43) Cant remove image id: 78605656-f77c-4b72-843b-1efef9644cf2 for VM id: aa21dd3c-6341-4d48-9819-112dbdf6f2db from domain id: 6682d31f-39ce-4896-99ef-14e1c9682585 due to: StorageDomainLayoutError.
2013-10-24 21:12:33,142 INFO [org.ovirt.engine.core.bll.RemoveAllVmImagesCommand] (pool-6-thread-43) Image id: 78605656-f77c-4b72-843b-1efef9644cf2 is not on a data domain and will not be marked as illegal.
2013-10-24 21:12:33,145 INFO [org.ovirt.engine.core.bll.RemoveVmCommand] (pool-6-thread-43) Command [id=e15c6804-d2e5-44b0-8fb9-6ad03421cd43]: Compensating CHANGED_STATUS_ONLY of org.ovirt.engine.core.common.businessentities.Image; snapshot: EntityStatusSnapshot [id=78605656-f77c-4b72-843b-1efef9644cf2, status=ILLEGAL].
The disk images are mounted on gluster storage through NFS.