I have a Genie HR44-500 with two clients, and it seems something similar is happening to me:
http://www.satelliteguys.us/xen/threads/odd-entries-showing-up-in-history-list-as-deleted.340467/
P.S. Similar situation to yours, see at least my later posts in linked thread as my ideas had developed some. One difference though is that the shows I wanted to record are not randomly getting deleted, just the randomly scheduled garbage is.
My machine misses all the usual suspected criteria: HDD nearly empty, not scheduling these programs, auto-scheduling working fine on a small amount of intended programs and not causing this, network cable disconnected, dish not shared, not subscribed to premium channels that are randomly getting recorded and deleted.