I'm pretty sure that anyone can record and release anything as long as they pay royalties to the original composers.
"Weird Al" Yankovic has always been clear that he doesn't legally *need* to get permission for his parodies but he always tries to obtain it because he doesn't want to upset anyone. And although there was a miscommunication regarding "Amish Paradise" that resulted in its release even though the original artist (whose name completely escapes at the moment) didn't want it, he's never issued any Prince parodies at all because Prince would never agree to any of them.
Publishing is where the real money is, which is why Elvis would demand a songwriting credit on much of what he recorded. He'd get a jillion bucks for his recording but he'd also get a cut any time someone else recorded the same song. I've also recently noticed that songwriting credits on old records don't always match the current entries in BMI/ASCAP, and suspect it's because someone has elected to redirect the funds elsewhere.