While I've never set it to that option, they should delete once you either click Refresh in the bottom corner of iTunes in the Podcasts section, or right click the specific podcast and select Update Podcast (I'm at work I can't verify actual wording) or when iTunes checks for new podcasts automatically, depending on how often you have it set to. I have it set to keep the 5 latest episodes and all of the ways I mentioned work deleting the oldest episode and replacing it with the new one.
What may also be the problem is that iTunes doesn't count it as played until you have watched the entire episode. If for example, you stop watching 30 seconds before the end because of advertisements or whatever reason, it won't count it as played.