[Plugin: JW Player Plugin for WordPress] By far the best Video-Plugin for WordPress

JW Player Plugin for WordPress is by far the easiest und most robust integration for Video into WordPress. It is quickly setup, highly flexible (flashvars, html5), especially for people with a lot of content who do their own encoding and hosting using playlists but also to use for single video embeds.

Update to the latest version, they fixed a lot of stuff!