You could also try encoding to flash video. Then you wouldn't have to send video anywhere, they could just view it online. You can get some pretty good quality from Youtube, and that other one I'm forgetting at the moment...

As for codec hell in Windows, like others have said, just use VLC. I'm sorry, Bitt, but codec packs are awful. They're just a mess, and there's really no way to uninstall what they put on. I definitely say install VLC and never worry about codecs ever again.

And I second the suggestion for Media Player Classic. VLC is lighter than most playback software, but MPC is the lightest I've seen that can play as many types of files. That, and MPlayer, which has some nice GUIs for Windows now.

All that said, I'm sorry Mark but are you sure that file is encoded properly? VLC definitely gave me an error when opening it, but it still played afterwards. That says to me: "encoding issue."