I understand ads are necessary for site revenue, as well as for actually informing people of more than the latest celebrity anti-acne aphrodisiac. But I live and work in the US: where any real business is stuck using T1 lines: streaming video kills those sites. Blocking Youtube is a broad-hammer: it has as much useful content, as it does junk. Video ads though: those hurt my network, period. Here's a way of resolving this situation...
* Review the list of DNS requests. If you're not using something like OpenDNS or Barracuda, you can have Wireshark or something monitor your DNS server for URL requests. On Linux routers, you may also be able to use netstat-nat or conntrack to do this.
* Found a decent listing of current video ad providers.
* Judicious use of domain tagging to see if certain domains were coming up in blocked categories or not.
* Visited popular websites + some of the ad provider sites (some didn't work). The properties from the Adobe Flash player, and the "Page Info" function in Firefox; help identify domains that stream video.
* Checked some domains against Google Safe Browsing to see if they were detected as having had malware. Google's own self-check is a rather amusing result: change the domain in the URL to test other ones.
Two things to consider regarding this kind of blocking. One, you don't want to block content inadvertently: many of the online media sources are used for streaming radio; which a number of my own users enjoy. Two, you won't get everything: the lists from 2009-2011 aren't even valid anymore; industry changes alter the list of active domains and providers on a regular basis.
A current block list I'm using at the moment of posting, minus category blocks...