A few weeks ago I was trying to track down a DHCP issue for some Lync Phone Edition clients. Tethered phones could sign in with no issues, but it didn't look like PIN authentication was working properly. We went through and validated all the DHCP options were present on the server, even removed and added them back, but would ultimately end up with "Certificate web service cannot be found" displayed on the phones. In order to isolate the problem a bit I started using the DHCPUtil.exe tool from a workstation (don't forget it must be x64 to use this) so I could simulate what the phones were requesting. You can copy the file from a Lync server and simply run DHCPUtil.exe -EmulateClient to simulate the options request process. While doing this I ran simultaneous packet captures on the workstation and DHCP server to see where the disconnect was.
After grabbing those traces it was pretty obvious something in the network path was preventing those responses from getting back to the client. The odd part was it wasn't preventing all parts of DHCP from working, since the clients could get an IP, gateway, and DNS information just fine - it was just the DHCP Inform message with the Lync options that was getting hosed.
We took those traces to the network folks and had them take a look at the Cisco switches in use. Low and behold, someone had previously left a couple DHCP snooping commands enabled in one of the switches, and that switch was dropping all of the DHCP Inform responses. We disabled that debugging feature and found the phones were able to sign in just fine.