It's happening on all 3 of my TVs/receivers, all of which are connected via HDMI
Bingo. I have a pile of engineering articles, many written by the actual developers of HDMI, all basically saying the roll-out of this 'technology' has been buggered by virtually every manufacturer in existence.
You need to run the S/PDIF toslink out of the DirecTV receiver/DVR out to your audio receiver/decoder. You'll never see (well, hear) any nonsense ever again. If you don't have a dolby decoder available at some locations (like a bedroom), run rca cables between the receiver/dvr and the display set, bypassing the HDMI for sound. You'll still have occasional sync/resync problems with the video, but it probably won't drive you nuts.
A couple years ago, I spent an entire week on the telephone with engineers from Samsung helping to narrow down HDMI problems on several models of their sets. Folks with a long history of HDMI with DirecTV products will know that Samsung displays in particular, had extreme problems when first released to consumers.
The upshot was mistakes (major ones) were made in the design of the HDMI chipsets by Samsungs fab plant in Korea. DirecTV, as well as other major HDMI consumer electronics 'sources' (like DVD player makers like Sony and Pioneer), basically played the dogs to the wagging tail of the HDMI chip makers. Luckily, DirecTV was able to figure some fairly fancy programming downloads into their receivers/DVR's, and make changes that eliminated most of the major problems.
But you don't mention WHICH SETS you have (i.e., which models). The 'original' models like the HR20-700, the H20-600/100's, and the like, have been mostly 'fixed' for quite a while. The newer stuff, like the HR21's and the like, I don't know, because I recommend to all the folks on the MDU companies I do engineering for to avoid them like the plague.
But try the analog audio hookups, and for the home theater, run toslink. See if you get 'off-sync' then. Then again, for some reason (say, as a licensed broadcast engineer for over 35 years) their's still problems (Chicago in particular keeps coming up in these forums), one can lay it at the feet of the stations not being required to have any engineers on staff since around 1984. Sad but true, and why I spent most of my career in the telecom industry, not broadcast (poof, there went 8 years of school almost down the drain).
Personally, I haven't seen any (ANY) sync problems for at least a year; but the broadcasters in my area tightened things up in a major way when several transmission problems hit them all about two years ago. Maybe that's what it takes, but for about 2-3 weeks every digital set around here with OTA went bonkers. And the HD feeds through DirecTV went a bit nuts too. But like lots of things today, nobody is really responsible for the problems, they only get fixed when it gets REALLY bad.