Reconnection problems after power cycle

I am having trouble with my XBee’s reconnecting after the power goes out and back on. We have XBees installed in places where the power will be off/on a lot, to simulate this we have connected the Xbees to timers to power on for 5-20 minutes and then off 5-20 minutes. I have been able to replicate the reconnecting issue this way, but I am unsure what to do next.

Here is my setup:
1 XBee 2.5 in AT mode, set as coordinator (power cycles every 15 mins), ATNI: COORD
1 XBee 2.5 in AT mode, set as router (power cycles every 5 mins), ATNI: REMOTE1

I have also added this to try to troubleshoot the problem:
1 Xbee 2.5 in AT mode, set as router (constantly on to monitor network), ATNI: DESK

I have both COOD and the DESK connected to serial porst of my computer, the other router is sending data when it is powered on to the coordinator.

I have found one instance where COORD is powered on, DESK is powered on, and REMOTE1 is powered off, and neither COORD or DESK see each other (ATND on both devices produce no results.) ATAI on both devices are 0, ATID on both devices are the same (3137).

What would cause this to happen, and is there anything else I can do to help find the cause of this?