Well, it started appearing that our problem was with DNS—namely that most of our clients were not being registered properly in DNS.
I found this thread: http://www.freewysemonkeys.com/modules.php?name=Forums&file=viewtopic&t=6433&highlight=dns
Which helped me fix that problem. I was optimistic that it would solve our check-in failures as well, but I’ve just confirmed that the problem is the same as before, with slightly more detail.
Clients check in once and then stop. I normally have check-ins set for every hour, but I’ve set them to 30 minutes to speed up the process so I can more easily notice patterns. After restarting the device, the initial check-in occurs. When the hour rolls around, it turns yellow (2 misses results in a yellow icon). After that they start to turn red and never check in until they’re rebooted.
The only exceptions are the clients which haven’t been restarted since they were registered in DNS. They continue to check in, but as soon as I restart them, they’ll check in once and then stop. I just don’t know what else to try at this point.