I switched to OpenELEC because there is a custom build by Rbej that supports usb hotplugging.
Xbmcremote successfully connects to this one via Zeroconf, very quickly!
Now, the next obstacle: music titles view is not shown in Xbmcremote
here's the output from terminal:
http://pastie.org/7676197

When I click on "titles" on XBMC itself on the Raspberry Pi, it also takes several minutes to load the list. I guess there must be something wrong with that in the first place.
However, after the RPi finally gets there, Xbmcremote *never* catches up: I gave it like several hours, but the titles list just remains empty.
This problem does not occur with albums, artists, etc., only titles.
The RPi/OpenELEC retrieves my music collection from an NAS via UPnP. The collection is large, but I'm sure nothing out of the ordinary, and a modern media player like XBMC should easily handle much larger libraries. Where is your RPi fetching the music files from?
I'm thinking maybe I should just try a SMB share...

Edit: this time it actually worked, some minutes after I posted this. I added the output to the paste.
Each title is shown 11(!) times in the list though. Some albums are also in the list multiple times. Some more output:
http://pastie.org/7676851