I am with Rob as long as if you do not re upload the video, and only embed it. I am sure the content provider would be fine with it. As long as he still gets stats from each viewer, of course linking back to his site is just good manners.
Now with that being said, If you run a site about porn,Tobacco, alcohol or other questionable things. Then it would be best to ask permission because they may not want to be linked to such things.