Just want to give my 25 cents..
We ran into something similar on our design. We put 3 DP83867IRRGZT RGMII PHYs on our custom carrier board (we pretty much copied the TEBF0808 design) on GEM0, GEM1 and GEM3. Following the datasheet, the resistor values we have put on the bootstrap pins was suppsed to give us the following MDIO address respectively : 4 8 and C. It turned out that in reallity, the two first PHYs responded to different MDIO addresses : 5, 9 and C.
In petalinux, in the device-tree, if you populate the reg property of the PHY (i.e. the MDIO address) , the MDIO subsystem is going to probe for exactly this address. Whereas if you don't populate the reg property, the subsystem will detect it and begin to scan accross all the addresses and stop at the first address where it reads something meaningful, meaning a phy responsed. Just by the way, turned out there is a bug in 2018.2 about this behavior that was fixed in 2018.3 : If you left the reg property empty, is yould only scan the first address and then exit the loop before scanning all addresses.
That being said, what I mean to explain is that I learned not to rely on the defined address for those chips. We don't use ethernet for u-boot ethernet boot so we didn't care about u-boot not finding the phy, we only cared about linux finding it, which it did after simply letting reg property empty and letting it scan the bus.
In the datasheet of the chip, it says that the internal resistor composing the voltage divitor at the bootstrap pins is 9K +- 25%, which is huge. That's why they say to use 1% resistors to implement the voltage dividor.
My guess is that the chip is just on the edge of responding to one address, and sometimes at boot, it picks up a slightly different voltage at its bootstrap pin and reepond to the next address. Try one address a above and one address below.
You could patch the source code of u-boot and scan all the mdio addresses at boot like in linux if you want something bulletproof
