As far as I know, once deletion is confirmed, the only way to recover it would be with a locally saved copy (.wfi or .wfx) or to pull a copy from your server backups.
Check the temporary files, maybe there may be a copy of the workflow there.
Thank you for the responses. We had no luck. We had to recreate our workflow. Sigh....
In the future, always try to backup your workflows from time-to-time. The best way to get the workflows and rules all in one go is to select Workflow > Export Workflow and select every workflow or groups of workflows.
When you export them all to that package you can date the file, then if you ever need to bring anything back you can open the package and select which workflow(s) you would like to import all from the same file.