Though not specific to music (and would have mostly non-music suggestions), you could hit suggestqueries.google.com with a jsonp-formed request. (maybe throw "music" in front of the typed query or something to apply filtering).
That's a good find. Though I don't know if Google's suggestions will fit into Apple iTunes search.