I'm afraid I've been seeing this issue too. My TiVo was hovering around the 50% used mark, and is a tad lower at the moment. I generally record HD content. A couple of programmes I've set as to record series, hold up to 10 shows, and was going to watch more as a series, have already lost a couple of shows

. Deleted items has also cleared itself, as have all suggestions. Something clearly gone awry.