Has there been anything introduced into the network lately that could be causing issues with DHCP?

What device/server/etc is providing DHCP for the phones?

How long are your DHCP leases for?

If memory serves correctly, a DHCP client should a renew request when 50% of the lease has expired. If it doesn't get an offer, then it should continue trying until the lease expires.