The message you get is that "The document may have been modifed by another user"

This is really similar to the CME error you get when someone edits an open invoice.  MY advice is to change the messsage to 

"Document has versions that may have been created by other users."  Indicating the user must delete the versions before deleting the  parent document.