I have had success downloading videos from youtube (as .flv files), adding them to my collection in the Zune PC software, and then syncing those to my player (Zune HD). The Zune software converts them before syncing. You should be able to sync videos to your phone in the same manner. Granted, you can't do this directly from the phone, but there is a workaround on the PC.
In order for the Zune software to recognize the .flv files as videos, you may have to edit your registry to set the ContentType of this file extension as Video. There are instructions for this on the Internet.