This was an issue in phone firmware as it turns out:
This is the BugID that is the most likely cause of the issues:
78xx Cannot join VLAN if broadcast over 30kbps
78xx Devices are not able to process CDP response to gain VLAN knowledge from switch when large amount of broadcasts (30kbps / approx 40 to 60 pps) on VLAN/Subnet are occurring.
The phone looks like it will still follow through with DHCP requests but will not accept the offered DHCP address due to the phone not knowing the VLAN structure.
** Issue does not occur when same amount of traffic is sent directly to the phone; only when it is broadcast traffic.
78xx on a switch port with a VLAN with a large amount of broadcasts occurring in subnet.
Reduce Broadcast traffic below 30kbps and reboot phone
Remove VLAN from Switch port that has the high Broadcast traffic.
Confirmed by only have access vlan on the switch port and phone registered and upgraded all perfectly fine.
My fix was to turn off spanning tree portfast on the port and it registers right away. Proceed with firmware upgrade after that. Turn SP back on.