I believe the copy funcitonality should still list the order even if it is voided, so you can create a new sales order and use the copy function to retrieve it.
I can only test in version 4, how are you deleting the order, what has happened to it previously? I just looked in the voided list and saw I could use the copy function on the orders in there, but it maybe how they are processed or the version that affects this.