I am making more progress now. WiFi sync has been working perfectly for more than 36 hours -- for the first time in more than 6 months!
[1] Unplug all Apple TV from network
[2] On my Mac, open Terminal and run "ping apple.com" continuously.
[3] Make sure iTunes is the active app on my Mac, and lock the screen by choosing "Login Window"
[4] Set all iOS devices to use static IP address
I suspect that my Mac (or my router) has trouble keeping its network connection up. By running the "ping", which sends one network packet per second, probably keeps the network up.
I also noticed that if iTunes is not the active app, it seems more "sleepy".
Now as soon as I plug my iPhone/iPad (both are 6.1.2) into charger, they start syncing immediately. Before, they would show the "looking for XXX's Mac" message for a few seconds, then start syncing (on a good day) or fail (usually).
More info:
I am running a Mac Mini basically as a file server and web server. It never sleeps. I rarely use it myself. But I allow my daughter to use it for 30 minutes per day. So she has a separate login session. So we have two login sessions on the Mac at the same time.
I also make sure that my daughter's account cannot launch iTunes or iTunesHelper (by making myself the owner of these 2 executables, and chmod og-rwx). In the past, whenever I plug in the iPhone onto the Mac, her account would start running a second copy of iTunes, and that probably confuses the whole wifi sync protocol).
Not sure if this will keep on going. I have my fingers crossed and will report any updates.