The TV app in ios 10.2 is showing deleted movies
Realised you're talking about the new TV app, sorry. 

The same method will work though. sign out of your iTunes account in Settings and then sign back in. 

*Your Apple TV might be using outdated data that hasn't refreshed yet. Sign out of your Apple ID on your ATV and ensure the movies are not on your account.

Then sign back in and only the movies you've purchased will show up.