Uh yeah, but Elvis' audiotapes exist and were sold off to a merchant.
Therefore Elvis' music still exists in the New Vegas universe and it wouldn't be too far off for them to be recoverable.
Besides, one could get around that just by not playing any songs where he specifically calls himself Elvis.