Have you tried testing whether or not iTunes is still “functioning excellent” as a DAAP server?
From what you describe, it seems unlikely to be an mt-daapd issue. The problem likely has something to do with the Rendezvous/Bonjour/zeroConf beacon. Either it is not broadcasting (i.e. not installed or configured corerctly on the Linux box) or the XP boxes are not detecting it (e.g. a firewall issue or the anomalous XP issue as described in the previously referenced thread). In order to determine which, you will need to analyze the traffic on your subnet.
Also, if your Windows machines are running SP2 and you have ICF activated, it will be necessary to ensure the required ports (DAAP, TCP 3689; mDNS, UDP 5353) are open to traffic.
Herman