Not sure what version of Outlook you are using and/or if using a PST file,
but if this "deleted items" folder is in a PST file you could try using the
Inbox repair tool (scanpst.exe) to verify that there are no issues with said
file.
Other than that, there are file and item count limits to PST files. If you
have exceeded the limits, then it is possible that actions like removing
items from the PST file would encounter errors.