It seems that youtube doesn't like people who load balance. Simply put, the IP that loads the webpage and probably the flash element needs to be the same one getting the video stream from one of their MANY servers.
The way I solved it was to bind certain IP ranges to a single WAN connection.
208.65.152.0/255.255.252.0
74.125.15.0/255.255.252.0
208.117.225.0/255.240.0.0
64.15.114.0/255.240.0.0
This seems to have gotten most of them. I may be missing a few or assigned too large a subnet, but at least my videos usually don't say "We're sorry, this video is no longer available" anymore.