Alternativen zu UDP und Multicast um Dienste zu finden

[chaosben]

Nehmen wir mal an, wir haben ein LAN, in dem UDP und Multicast "verboten" ist oder "nicht unterstützt" wird. (Das sei ein Fakt, über den wir nicht diskutieren brauchen).
Und nehmen wir an, ich will mit möglichst wenig Aufwand (aka: zero-config) bestimmte selbstgeschriebene Dienste (die sich auf versch. Servern tummeln) in diesem Netz finden.

Welche einfachen (und dadurch robusten) Möglichkeiten gibt es dafür?

Eine Variante wäre ein bestimmter Hostname, der bei Hardwareänderungen angepasst wird. Das ist mir aber zu umständlich (Admin betteln) und zu langsam (DNS-Cache).