For now, there aren't too many non-Flash videos indexed by Google: .edu sites and NASA seem to have priority.
* Caching web pages is a notable exception
And here's an excerpt from a web page that link to the AVI (the fourth search result). Google doesn't link to this page, but you can find it using a normal Google search:
Other video search engines, like Live Search and Yahoo Video, already include videos from the web, but none of them figured out how to get information about videos, rank them and present them properly. And Google Video is no exception, considering that YouTube dominates the search results for almost any query and that the ranking algorithms use information about the number of views and ratings, which is only available for some video hosting sites.