I believe that it would be intuitive to jump to the beginning of each and every letter. For your example, I would expect to proceed to the Baha Men.
When I search for a particular artist, I ask, "Which letter does this artist's name begin with?", then proceed/skip to that letter set, and then I expect to parse alphabetically within that set to the artist's name. It probably makes the most sense to stick with an alphabetical sorting and parsing method at all times.