Just wanted to provide a followup on this. Reached out to Seeed and they said they would order a camera and investigate further.
I also had some success on the Nano by reducing the cable length between the Nano and the camera (using a CSI-HDMI adapter from Arducam). Worked sometimes on first boot. Then stopped.
Regardless, we are nearing a deadline and decided to switch to the Xavier for a prototype. The Nano has been challenging due to reduced support from NVIDIA.
I believe you are right about device tree. Something different from first boot compared to reboot. Even with the longer cable, it was 100% consistent with this strange behavior.