Luis, in answer to your question, "yes", if your performance is slow, I think you might gain significantly by deleting thousands of orders and clearing deleted messages.
I am not sure why it takes so long to delete those orders. Are you using the method David describes above? If so, perhaps you should select a year or so's worth, and delete them at the end of the day. I bet if you come back in an hour they will be gone; if not, they should disappear over night. Once you "select and delete", you don't need to watch the process.
