In theory the games are always there to re-download (bought or PS+'ed). But I guess if Sony's licenses expire the game may become unavailable. I think I've only had dynamic themes on the PS3 disappear when I upgraded from a 320GB to 750GB.
(I had a 320GB 7200RPM with 16MB cache, there was only a small improvement but I decided to stick with 7200RPM/16 and 1TB 7200 drives weren't available then, so went with 750)
If you've ever purchased something, you can go redownload it (PSN Store->View Downloads->scroll a listed sorted by date.) The only exception is like cringe said, if they Sony loses the rights to it for some reason and that's very rare. There was a Teenage Mutant Ninja Turtles Arcade game that was taken down for that reason (and it might have been the publisher's issue), but that's the only one I can recall.
The games/extras offered in PS+ do change fairly often, especially the full length games. The best way to game it is to always leave some extra space on your hard drive so you can download anything you might be interested in, delete it to reclaim the space, and then it'll remain in your download list long after it's been shuffled out of PS+.
The game looks to be still on (I assume you are talking about the game and not the TV show). This celebrity list was just released a couple of days ago, and the game is still listed on the manufacturer's website as 'coming soon'.