I believe the movie PERFECT (John Travolta, wasn't it?) had a replacement
score on video either because the rights to the songs were too expensive or
some related reason.  I recall a complaint to a video magazine at the time.
I'd like to know more such examples.
 
The Illinois lottery is running a commercial right now based on the expense
of getting original material--they're joking around with alternative
versions of "Jumping Jack Flash."