It's my understanding that iTunes only keeps the 300 most recent episodes of any podcast. My rule of thumb is if I download a podcast I really like through iTunes, I go into my iTunes media folder (Music > iTunes > iTunes Media > Podcasts) and copy the file(s) off to a different drive for safe-keeping. The ONE time I didn't do this was for 5x5, the feed for which later broke. Thankfully (after a few emails and lots of waiting) the 5x5 feed has been restored, I was able to download them all via iTunes again and they're now copied off to an external drive.
As for premium podcasts, the only one I've had experience with was Skeptoid. Since they sent me a USB-drive with every episode up to that point (590or so), I only paid attention to the newer episodes in iTunes. I don't remember if all ~590 were in the paid iTunes feed or it it was just episodes 290-590. The only reason I paid for the membership was to have the back-catalog. I'd have paid for SGU Premium if they had a similar model, but luckily they have every episode available for individual download on their site. It's more time-consuming but at least it's free. Now that I think about it, I did subscribe to Coast To Coast AM's premium feed for a few years but that's a different story altogether. I can't remember how far back their episodes went as I've since tried to block it from memory...
