I have NEVER gotten the official Tivo app to locate my TivoHD or my XL4. Yes, I have NRC turned on. They are both hard wired to a switch which is connected to my wireless router. Previously they were wired directly to the router and the app still didn't see my Tivo's. Very frustrating. I use RCX for Tivo
because it allows you to set the IP address of your Tivo manually if needed. It's not the prettiest UI, but it works. If the Tivo app had this feature, I'd been using it a long time ago.
Update: Ignore everything I just said, one of the more recent updates must have fixed the issues I was having with my particular router/network. The Tivo app works now!