i know that u were only using jay z as an example, but in case you were interested, you can get the full black album acapella version. they sell it at tower and places like that. just in case u didn't know.
but yeah, there's no program that does it very well. i bought Audacity on eBay a few years ago because it claimed to be able to do it. here's how they said to remove vocals from instrumental tracks. they claimed that if you did the opposite, it'd work.
http://audacity.sourceforge.net/help/faq?s=editing&i=remove-vocals
it didn't work for rap tracks. sometimes it worked for hooks but the sound quality was terrible. it worked sometimes for other genres of music but the recording process in rap is different than most others.