Several years back, as a condition of being allowed to use a specific wireless spectrum license, the FCC mandated that Verizon unlock all LTE capable phones from day one. This was well before eSIM. Verizon phones were sought after because they came unlocked as a result of this mandate.
A few years ago, Verizon successfully argued to the FCC to be able to hold off unlocking. I forget what the original amount of days were, but they eventually settled on 60 days which is the current policy. That include eSIMS.
So, buy a Verizon iPhone, it automatically unlocks after 60 days whether you've paid it off or not. It helps to know each carrier's unlock policy. They post them online.
Your iPhone would have been unlocked 60 days in, not because you paid it off 6 months later. What happened IDK. It's eSIM and I have yet to experience the 'joys' of using eSIM (I'm still using physical SIM cards). But your phone should have been unlocked long before this - because Verizon/spectrum license/FCC.