Microsoft is adding support for industry standard video and audio formats in Windows 7, after 6+ years of ignoring them. This has a full list of what is being supported.

Though, as you pointed out, it won't help if the intended playback platform isn't Windows 7, OS X, or Linux, without having to manually add codecs.

As for the deinterlacing issue, I don't really have an answer there. All my video work has been on OS X, and with progressive scan formatted videos.