How to make DHCP domain name registration work with OS X

Not understanding whats exactly your problem. Maybe this can help you.

If you set the search option, in your own config (network->advanced->dns->search domains) or by your dhcp server. You basically eliminate the need to add this part to a fqdn.

Example:

search: foo.com

then,

ping test

would try to resolve test.foo.com

So, in your case that would be test.my.example.com

Futhermore, setting your local name, you can change under:

Sharing -> Edit...

I use a Time Capsule as my Wifi router, and all my devices are registered in the domain (e.g. "lan") once a device has a lease and each device receives the "lan" domain as the search domain as part of the DHCP config.

Pinging 192.168.0.xxx, iPhone4.lan, just iPhone gets me to my device.

If you can ping the devices by IP address and not by name, then the answer lies more in your home network than in the devices themselves, and how the DHCP server registers device names once a DHCP lease has been obtained.

If your Windows machine has a static IP address, then its quite possible all you need to do is add the Wifi Lan name into the DNS Search config on the Windows PC, but more information is needed on how you are configured.