In short: How to reliably discover a server running somewhere on a (presumably multi-segmented) local area network with zero client configuration

My client application has to locate the server application without knowing the server IP address. It has to work on a local LAN that may be split into segments with hubs or other switching devices.

I already have a working solution, but it is a bit cumbersome to get it working on multi-segment networks. It works as follows:

When the client starts up, it sends UDP broadcasts on its own network segment. If the server is running on the same segment, it works without any issues - the server responds with the appropriate messages.

If the server and client are running on networks separated by a hub / switch that won't forward UDP (the most likely case), then I have a server instance running on each segment, and they forward client requests to each other via TCP - but I need to configure this for the server instances (simple, but still a pain for tech support.) This is the main problem that I need to address. There are sites where we have hundreds of clients running on 5 or 6 separate segments.

The problems I'm facing:
1. Although my application installer enables the appropriate ports on the firewall, sometimes I come across situations where this doesn't seem to happen correctly.
2. Having to run multiple server instances (and therefore configure and maintain them) on hub/switched networks that won't forward UDP

Finally I need a solution that will work without maintenance on a minimal Windows network (XP / 2000 / Vista) that probably doesn't have Active Directory or other lookup services configured.

I don't want to tag on any runtime stuff for this - should be able to do it with plain VC++ or Delphi.

What approaches do commercial apps usually take? I know that SQL Server uses a combination of broadcast and NetBEUI calls (I may be wrong about this).

Thanks in advance.