Right, I've tried to reproduce this with the help of my laptop. After configuring it to make a wireless connection (with the iwl3945 Intel PRO/Wireless driver) on boot, outside of NetworkManager, and installing patched mt-daapd it successfully appears on a wired client's shared library list in Rhythmbox from a fresh boot.

Relevant lines of the syslog look like this:

May 16 16:13:59 ceres dhclient: Listening on LPF/wlan0/00:1c:bf:90:a4:c0
May 16 16:13:59 ceres dhclient: Sending on   LPF/wlan0/00:1c:bf:90:a4:c0
May 16 16:13:59 ceres dhclient: Sending on   Socket/fallback
May 16 16:13:59 ceres dhclient: DHCPDISCOVER on wlan0 to 255.255.255.255 port 67 interval 4
May 16 16:13:59 ceres kernel: [   17.384085] wlan0: authenticate with AP ffff88007d0bfac0
May 16 16:13:59 ceres kernel: [   17.385975] wlan0: authenticated
May 16 16:13:59 ceres kernel: [   17.385980] wlan0: associate with AP ffff88007d0bfac0
May 16 16:13:59 ceres kernel: [   17.388574] wlan0: RX AssocResp from ffff88007d951026 (capab=0x411 status=0 aid=1)
May 16 16:13:59 ceres kernel: [   17.388580] wlan0: associated
May 16 16:13:59 ceres kernel: [   17.390822] ADDRCONF(NETDEV_CHANGE): wlan0: link becomes ready
May 16 16:13:59 ceres mt-daapd[2753]: Firefly Version svn-1696: Starting with debuglevel 2 
May 16 16:13:59 ceres mt-daapd[2753]: Error loading plugin /usr/lib/mt-daapd/plugins/ssc-ffmpeg.so: /usr/lib/mt-daapd/plugins/ssc-ffmpeg.so: undefined symbol: avcodec_decode_audio 
May 16 16:13:59 ceres mt-daapd[2753]: Error loading plugin /usr/lib/mt-daapd/plugins/ssc-script.so: plugin declined to load 
May 16 16:13:59 ceres mt-daapd[2753]: Plugin loaded: daap/svn-1696 
May 16 16:13:59 ceres mt-daapd[2753]: Plugin loaded: rsp/svn-1696 
May 16 16:13:59 ceres mt-daapd[2753]: Starting signal handler 
May 16 16:13:59 ceres mt-daapd[2760]: Starting rendezvous daemon 
May 16 16:13:59 ceres mt-daapd[2760]: Client connecting 
May 16 16:14:00 ceres mt-daapd[2760]: Initializing database 
May 16 16:14:00 ceres mt-daapd[2760]: Full reload... 
May 16 16:14:00 ceres avahi-daemon[2813]: Found user 'avahi' (UID 110) and group 'avahi' (GID 119).
May 16 16:14:00 ceres avahi-daemon[2813]: Successfully dropped root privileges.
May 16 16:14:00 ceres avahi-daemon[2813]: avahi-daemon 0.6.23 starting up.
May 16 16:14:00 ceres avahi-daemon[2813]: Successfully called chroot().
May 16 16:14:00 ceres avahi-daemon[2813]: Successfully dropped remaining capabilities.
May 16 16:14:00 ceres acpid: client connected from 2785[0:0] 
May 16 16:14:01 ceres avahi-daemon[2813]: No service file found in /etc/avahi/services.
May 16 16:14:01 ceres avahi-daemon[2813]: Network interface enumeration completed.
May 16 16:14:01 ceres avahi-daemon[2813]: Registering new address record for fe80::21c:bfff:fe90:a4c0 on wlan0.*.
May 16 16:14:01 ceres avahi-daemon[2813]: Server startup complete. Host name is ceres.local. Local service cookie is 2860126817.
May 16 16:14:01 ceres avahi-daemon[2813]: Registering HINFO record with values 'X86_64'/'LINUX'.
May 16 16:14:01 ceres mt-daapd[2760]: Client running 
May 16 16:14:01 ceres mt-daapd[2760]: Client registering 
May 16 16:14:03 ceres dhclient: DHCPDISCOVER on wlan0 to 255.255.255.255 port 67 interval 9
May 16 16:14:03 ceres dhclient: DHCPOFFER of 192.168.1.21 from 82.70.152.20
May 16 16:14:03 ceres dhclient: DHCPREQUEST of 192.168.1.21 on wlan0 to 255.255.255.255 port 67
May 16 16:14:03 ceres dhclient: DHCPACK of 192.168.1.21 from 82.70.152.20
May 16 16:14:03 ceres avahi-daemon[2813]: Joining mDNS multicast group on interface wlan0.IPv4 with address 192.168.1.21.
May 16 16:14:03 ceres avahi-daemon[2813]: New relevant interface wlan0.IPv4 for mDNS.
May 16 16:14:03 ceres avahi-daemon[2813]: Registering new address record for 192.168.1.21 on wlan0.IPv4.
May 16 16:14:04 ceres dhclient: bound to 192.168.1.21 -- renewal in 1591 seconds.
May 16 16:14:04 ceres mt-daapd[2760]: Starting mp3 scan 
May 16 16:14:04 ceres mt-daapd[2760]: Starting playlist scan 
May 16 16:14:04 ceres mt-daapd[2760]: Updating playlists 
May 16 16:14:04 ceres mt-daapd[2760]: Error scanning MP3 files: No such file or directory 
May 16 16:14:04 ceres mt-daapd[2760]: Scanned 0 songs in 0 seconds 
May 16 16:14:04 ceres mt-daapd[2760]: Starting web server from /usr/share/mt-daapd/admin-root on port 3689 
May 16 16:14:04 ceres mt-daapd[2760]: Registering rendezvous names 
May 16 16:14:04 ceres mt-daapd[2760]: Serving 0 songs.  Startup complete in 0 seconds 

You can see mt-daapd and avahi-daemon starting concurrently before an IP has been associated with the wireless interface. As soon as it does, Avahi registers itself on the interface and the service appears on the network.

It's possible that this load order doesn't reproduce the race you are experiencing or that the problem lies elsewhere. But that's where my assistance must stop, I'm afraid, since without a reproduction I would not be able to trace the problem. :(