's because sometimes they DO have to beg or buy permission.
The few people I know that have been signed have had to work through either of two deals.
For those whom the label doesn't seem to really feel have 'legs' (in other words, this may sell a bit, but they don't feel that the band has much potential beyond the initial strip mining), they seem to get signed to 'x number of albums' contracts - normally one or two, but with embedded text to give the label first rights to a certain amount of additional recordings.
For those whom the labels seem to think have potential beyond 'flash in the pan' status, there is an 'exclusive rights' contract. Admittedly, this DOES funnel a small extra amount of money to the artists, but it also means that ANY work done during this period that is recorded is the automatic property of the label - whether or not they have anything to do with the project.
So in these cases, the artist WOULD need the label's permission to appear on the works of another label's artist or compilation thereof.
It's all about not owning the rights to your own work. The 'Sonny Bono' extension thread has great info on this, but I'm lazy and depressed thinking about it, and don't have the link ready...