Bizzach,
Protecting a show does sort of keep it from being deleted. When you try to delete a protected show it will prompt you for a password. Then, if you enter the correct password it will prompt you again (Y/N) for if you want to delete it. That makes it pretty hard to delete a show on accident.
dcmcgo,
The whole thing sounds a little strange. If you didn't delete it, it should still be there. Maybe it's a fugazi. Try rebooting the unit (hold the power button on the receiver for 5-10 seconds until the unit reboots). Maybe it will come back again (providing you didn't really delete it in the first place).