It's been more than a year since the post about in-video banner ads, an idea that YouTube eventually implemented and that has become a standard offering on other video sites. Here's one other thing they could try: ads on the interactive last frame that, on YouTube, promotes related videos.
Most of the existing video ad formats have their problems: pre-rolls are annoying, in-video banners are rarely relevant to the content, and post-rolls have nothing to click on. Last frames could work because they are not interruptive and offer users something to do after they are done with their primary activity -- watching the video.
Idea: How to put ads into YouTube
Follow-up: Embedding Ads into YouTube Players