For future use - this is radical, but if the cost is that great:
Immediately upon realizing the mishap (deleting a sheet that is not saved anywhere), crash Excel with a Task Manager or a task killer, or if you can't do that, unpower the PC (any way other than with the PC's "on" button). Restart, take the auto recover file, and see if your data is there.
Auto recover information is collected/updated periodically, and you may land in between updates if the fates fell such. The interval is shown in menu Tools/Options/Save in XL07 (probably same for earlier versions).
Personally I don't trust autorecovered files, suspicious of them being corrupt (which is severe and subtle and should be avoided). You might want to just paste the recovered data to a new workbook, which is what I do in that case. Others think nothing of going on with autorecovered files (say, after a power outage), so it's up to you.
Again, this is radical, and may not be worth it unless the loss is high otherwise.
As I recall, Autorecover is available in XL00+; I know it's in XL02+