I kinda suspected that the real limit was total data instead of songs. I mentioned that in my bug report but their response didn't acknowledge it.
Your advice on cleaning up data is good. I've been extremely meticulous with my metadata; I almost always have to clean up the crap that Gracenote sends. But then, I work in a library. Too bad Music Beta doesn't use the "sort artist" field.
I still wonder what's being streamed back. The specs say that FLACs are transcoded into 320kbps MP3s. If AACs are also transcoded to MP3 then the sound quality will suffer. What I heard streamed in my car was definitely inferior to the ALACs I usually hear.