The great thing about having a budget for music, as we know, is getting a score written specifically for the film, one that builds the atmosphere and gives that emphasis to the cutting. Not many of us get that pleasure. So start with the music or find the music to suit? I would never start with the music because I work primarily with the story and cut to tell that. Which means that I compromise about the music and have to spend a lot of time on getting something that contributes to the sequence. Always wish that I had practised seriously for my childhood music lessons -- too late now!

I employ the usual 3 approaches:
1) find something reasonably suitable from ready made royalty free sources;
2) use something like Cinescore to adjust pieces from a data base;
3) create a suitable track using software such as Acid Pro (using pads and samples).
My first cut is without music, but at an early stage I want something behind there to assess the mood of the assembled scene. This is where you take something on hand and can soon find it so well integrated that you have trouble later replacing it -- OK if you can get permission and can afford the royalties. So, which of the 3 options above works best? Unfortunately that is highly variable. I've had great atmospheric matches from the Twisted Tracks and the Vzone libraries. I've been able to coerce good tracks out of Cinescore, although usually I want to give it commands rather than hints about empahsis. Acid Pro is a powerful tool, but most powerful at the finger tips of those who really did pay attention to their music lessons. But even I have done good stuff with Acid, most recently incorporating music pads from VASST and the Sony sample library.
Maybe that contributes something in answer to your question. Editing is never finished until all tracks are locked, so of course the music will influence the cuts even if visuals are primary. And as always, "it depends". If it is a music video, that is laid down first.