If a node type's 'Create new revision' is enabled and the $user does NOT have 'administer nodes' permission, she cannot edit the nodes of this type without creating a new revision, regardless the fact that she is granted the 'delete revisions' permission. IMO if the $user is allowed to delete revisions, then she should even be allowed to edit the nodes without creating a new revision.
I was even thinking about taking the 'revert revisions' permission into account. If the $user is only allowed to revert revisions, but not delete them, then she is not allowed to hide her own edits from the history, so granting her the 'revert revisions' by itself should not allow her to edit a node without creating a new revision. OTOH if she is granted the 'delete revisions', but not the 'revert revisions' permission, then she can hide the fact that there was a revision before her own one, anyway.
In short, it is kind of usability improvement: allow the $user to edit a node without creating a new revision if she can hide the fact that there was any previous revisions before her own one (by deleting the old ones). The attached patch does this.
FAILED: [[SimpleTest]]: [MySQL] Unable to apply patch allow_unrevisioned_edit_with_delete_revisions.patch. Unable to apply patch. See the log in the details link for more information. View