I wouldn't mind that to be honest. And I've discovered some shows/ movies which were pretty damn good (but not mainstream) just based on this sort of logic. I most likely would've never discovered them otherwise.
I'd much rather see an acknowledgment that the show exists and that they don't carry it, and a list of related titles separated by actor, genre, director, etc. If contract allows, they could even include a "Coming on %month %date" if a licensing agreement has been reached but is not yet active. That might make me just wait until they have the title and find something else to watch now, rather than checking if (say) HBO has the movie. Additionally, they could have a "request this title" button, even if it does nothing because they're already basing their leasings on search data.
I'd also like a list of places I can view it a la gowatchit.com, but I can understand why they don't do that.