Address randomization helps but it's not enough. The phone still transmits at a regular cadence so it's pretty easy to figure out which old address has changed into which new address and keep tracking the same device.
Maybe not easy, but also not hard. The only thing that screws you up is someone playing with the airplane mode toggle of their phone while moving within your detection radius.