1. What version of AOS are you running and integrated or overlay design?
2. Are you doing Location restrictions?
From the symptom, it sounds like you are hitting the max 64 mDNS devices that an iOS device can display. That doesn't just mean AppleTVs. If there are other mDNS servers (printers, iTunes, etc) that are being allowed, then the iOS device will only display a random assortment of AppleTVs.
Also, make sure you have enabled the CPPM Registration Required option on the controller. This will block non-registered mDNS servers from clogging up the iOS device.