New plugin brings HTML5 video support to Internet Explorer
At least you were out of luck. Developer Christian Adams has created a plugin that brings a sliver of the functionality (the video tag) to IE. It's still considered a preview release at this point -- there are no playback controls and you need to specify an attribute within the <video> tag to enable IE playback.
Who knows, maybe Microsoft will bolt on support with an IE update at some point in the future. Maybe it'll be included in IE9. If not, Adam's plugin is taking shape nicely and should give users who want to take advantage of the <video> tag a viable option.