I've not done the above, but I've released both games and music albums so I have some idea what you might have to deal with here.
The main issue you have is that the ownership of the music for a typical signed band is very complex. There are at least 2 types of copyright (composition and recording), which are often controlled by separate entities, neither usually being the artist themselves. As such you won't be able to get permission from the band as they won't be in a position to give it. The publishers and/or rights management agency may be able to sell you licences, but whether specific licences exist for game use, and worldwide, you can get worldwide, is another matter. TL;DR this is a very slow route and potentially expensive.
If you work with unsigned bands, it can be a lot easier. They may still however have signed away some rights to a copyright collection society which means you're back in the land of having to buy a licence. If they haven't done so, then they'll be able to give you permission for distribution, in which case there should be no legal problems.
Regarding what is a 'fair' rate, no such thing exists. Lesser-known acts tend to be grateful just to get the promotion, and well-known acts have this taken out of their hands (as above).
As for your last question... surely almost soundtracks are 'collaborations with musicians'. Is there some more specific definition here that you mean?
I can imagine going through licensing groups would cost a small fortune (up-front AND royalties), especially for a game that is made on a more independent level. Perhaps that level of thinking would require much more investment and could be unreasonable to start. Thanks for pointing that out.
But, when I think about the music industry as a whole, there's a lot of unrecognized talent out there that would love the exposure (and isn't represented by ASCAP or BMI.) This is the kind of talent I'd rather reach out to, and since most musicians at an unrecognized level are typically broke, I feel like compensation helps the artist as well, creating a good relationship between parties. While some bands may say "oh don't worry about paying us" and play the gracious card, most unrecognized touring bands still need the gas money to make it to the next show. Whether the compensation is done via lump-sum or based on revenues may or may not be relevant, I don't know for sure.
And the 'collaborations with musicians' line did sound a bit vague, I apologize for that, but I was referring to 'established recording artists' or say, reaching out to a metal band (signed or unsigned) to help generate a metal/rock-sounding OST with you.