A general file undelete tool *might* be able to recover it if no data has been written to the drive after that file got deleted (which usually is unlikely on a media center since you tend to record TV shows etc.).
If other writes have happened it's probably gone forever....
I ran into the same problem with BeyondTV in XP Pro. I accidentally deleted a recording and found absolutely no trace of it when I tried using a data recovery program. I don't know if this is a trend with PVR programs or not but I wish they'd have some means to recover deleted shows.
Now the real test will be to see if it retains any shows I delete within BeyondTV. My next stop will be the Snapstream Forums to see if there's a setting I can change within BTV to avoid this.
I just checked the Snapstream Forums and it appears that shows are deleted just like kapone said. They get deleted directly because they are too big for the Recycle bin. Typically the Recycle bin is set for 10% of the size of the drive by default. Since I have a 750GB drive for my recordings I would assume that my Recycle bin is more than adequate to hold a 1- or 2-hour deleted program. I guess I'll need to do a little digging when I get home to see what's up.