My Hue bulbs are the “original” (3rd gen I think) before Bluetooth was a thing…but I just walked through this whole exact same thing and I could not get them to reset with any number of power cycle routines.
The only way I could get them to actually pair with my HA/Z2M was to manually add them to my old hub (long story why they weren’t already in there), and then delete them.
Yes, it was a pain. But it worked well and once I got the process down I just did 3-5 at a time and worked through them all. YMMV.