A bit of an aside, as clearly latency is an issue with the downlinks arriving too late (possibly/probably also indicating that the uplinks take too long to arrive at TTN):
This might actually be weird. Assuming the device does not do an OTAA Join for each of its uplinks (don’t!), it should have no reason to initiate a new join (immediately) after a gateway was rebooted. Also, when not doing any downlinks, latency is not an issue. So, if all this started due to rebooting the gateway, then apparently the device requires downlinks to work, which might have made it reboot itself when it saw that it got no downlinks? Like: does it send confirmed uplinks? Also ADR might make it detect that downlinks are missing for some extended period?
So: how soon after the gateway’s reboot did the problems start? (And how often is the device transmitting?) Why was the gateway rebooted?