"...the conclusion that DHCP just doesn't work on OSX in a heterogeneous network..."
I'd be very surprised if it REALLY doesn't work. Chez moi I have a FreeSCO router dishing out DHCP addresses to 2 XPs, a Win98 and a SuSe Linux 9 boxen which all accept it without any fuss. Something ain't configured right somewhere. Can you establish who the browse master is?