Great question and I have had the same problem with another client of mine... I would suggest 2 things. 1. Build a Video sitemap for Google and submit it to your webmaster tools account. More information can be found on Google's website http: //www.google.com/support/webmasters/bin/answer.py?hl=en&answer=80472
2. I would recomend the company build a YouTube Channel if you have not already done so.
Meta Data is also important within the video since it normally is created from the software you are using to render such as CS4 Adobe Premiere. As the engines gain more experience scrubbing video files this could help even more in the future.
Hope this helps, Good Luck
