This was happening to me when I had TiVo. I just assumed it was an accepted issue as nobody ever seemed to mention it. I would just go into everything I recorded thereafter and update the status of each recording not to delete until I delete.
Not a problem I've had with SKY. With only 250Gb of hard drive space, you tend to watch stuff pretty snappy
