the soundtrack for vice city comes in the form of six or seven cds i believe. each one featuring a different radio station. or as a complete box set. the last time i checked they were not deleted but listed as 'unavailable'
if its any use to you at all, i have a promo cd sampler of the music from gta3 (game before vice city) containing 35min continuos mix of the tracks from this game.
if you want it, click the little envelope next to my name and i will send it to you gladly Robotic_Rob